本系列文章將于2021年整理出版，前驅教材：《演算法競賽入門到進階》 清華大學出版社
網購：京東 當當 ??作者簽名書：點我
有建議請加QQ 群：567554289

1. 分塊概念

?? 回顧“區間”問題，前面給出了暴力法、樹狀陣列、線段樹等演算法，給定一個保存n個資料的數列，做m次“區間修改”和“區間查詢”，每次操作只涉及到部磁區間，暴力法只是簡單地從整體上做修改和查詢，復雜度O(mn)，很低效，樹狀陣列和線段樹都用到了二分的思想，以O(logn)的復雜度組織資料結構，每次只處理涉及到的區間，從而實作了O(mlogn)的高效的復雜度，
??雖然暴力法只能解決小規模的問題，但是它的代碼非常簡單，
??有一種代碼比樹狀陣列、線段樹簡單，效率比暴力法高的演算法，稱為“分塊”，它能以$O(m\sqrt{n})$O(mn?)的復雜度解決“區間修改+區間查詢”問題，簡單地說，分塊是用線段樹的“磁區”思想改良的暴力法；它把數列分成很多“塊”，對涉及到的塊做整體性的維護操作（類似于線段樹的lazy-tag），而不是像普通暴力法那樣處理整個數列，從而提高了效率，
??用一個長度為n的陣列來存盤$n$n個資料，把它分為$t$t塊，每塊長度為$n\mathrm{/}t$n/t，下圖(1)是一個有10個元素的陣列，共分成4塊，前3塊每塊3個元素，最后一塊1個元素，

??對比塊狀陣列與線段樹，線段樹是一棵高度為logn的樹，塊狀陣列可以看成一棵高度為3的樹，見圖(2)，從圖(2)可知，在線段樹上做一次操作是$O(logn)$O(logn)的，因為它有logn層；分塊是$O(n\mathrm{/}t)$O(n/t)的，因為它把資料分成了$t$t塊，處理一塊的時間是$n\mathrm{/}t$n/t的，下面介紹分塊演算法，并詳細說明復雜度，

2. 分塊演算法

??塊操作的基本要素有：
??（1）塊的大小，用block表示，
?? （2）塊的數量，用t表示，
?? （3）塊的左右邊界，定義陣列st[]、ed[]，用st[i]、ed[i]表示塊i的第一個和最后一個元素的位置，st[1] = 1，ed[1] = block；st[2] = block+1，ed[2] = 2×block；…；st[i] = (i-1)*block+1，ed[i] = i*block；…
??（4）每個元素所屬的塊，定義pos[]，pos[i]表示第i個元素所在的塊，pos[i]=(i-1)/block + 1，
?? 具體內容見下面的代碼，其中每塊的大小block的值等于$\sqrt{n}$n?取整，后面的“復雜度分析”會說明原因，如果$\sqrt{n}$n?的結果不是整數，那么最后要加上一小塊，代碼中重要的內容是處理這個問題，

int block = sqrt(n);          //塊的大小：每塊有block個元素，
int t = n/block;              //塊的數量：共分為t塊
if(n % block) t++;            //sqrt(n)的結果不是整數，最后加一小塊
for(int i=1; i<=t; i++){      //遍歷塊
    st[i] = (i-1)*block+1;
    ed[i] = i*block;
}
ed[t] = n;                    //sqrt(n)的結果不是整數，最后一塊較小
for(int i=1; i<=n; i++)       //遍歷所有元素的位置
    pos[i]=(i-1)/block + 1;

??用分塊解決區間問題很方便，下面以“區間修改+區間查詢”（洛谷P3372）為例，
?? 首先定義區間有關的輔助陣列：
?? （1）定義陣列a[]存盤資料，共n個元素，讀取初值，存盤在a[1]、a[2]、…、a[n]中，
?? （2）定義sum[]，sum[i]為第i塊的區間和，并預處理出初值，

for(int i=1; i<=t; i++)                 //遍歷所有的塊
    for(int j=st[i]; j<=ed[i];j++)      //遍歷塊i內的所有元素
        sum[i] += a[j];

??（3）定義add[]，add[i]為第i塊的增量標記，初始值為0，
?? 然后對數列a[]做“區間修改+區間查詢”操作：
?? （1）區間修改：將區間[L, R]內每個數加上d，
?? 情況1，[L, R]在某個i塊之內，即[L, R]是一個“碎片”，把a[L]、a[L+1]、…、a[R]逐個加上d，更新sum[i] = sum[i] + d*(R - L + 1)，計算次數約為n/t，
?? 情況2，[L, R]跨越了多個塊，在被[L, R]完全包含的那些整塊內（設有k個塊），更新add[i] = add[i] + d，對于不能完全包含的那些碎片（它們在k個整塊的兩頭），按情況1處理，情況2的計算次數約為n/t + k，1 ≤ k ≤ t，
?? 總結兩種情況，處理整塊時，只更新sum[i]，不更新add[i]；處理碎塊時，只更新add[i]，不更新sum[i]，

void change(int L,int R,int d){
    int p = pos[L], q = pos[R];
    if(p==q){                      //情況1，計算次數是n/t
       for(int i=L;i<=R;i++)  a[i]+=d;
       sum[p]+=d*(R-L+1);
    }
    else{                          //情況2
       for(int i=p+1;i<=q-1;i++)    add[i]+=d; //整塊，有m=(q-1)-(p+1)+1個，計算m次
       for(int i=L;i<=ed[p];i++)    a[i]+=d;   //整塊前面的碎片，計算n/t次
       sum[p]+=d*(ed[p]-L+1);
       for( int i=st[q];i<=R;i++)   a[i]+=d;   //整塊后面的碎片，計算n/t次
       sum[q]+=d*(R-st[q]+1);
    }
 }

??（2）區間查詢：輸出區間[L, R]內每個數的和，
?? 情況1，[L, R]在某個i塊之內，暴力加每個數，最后加上add[i]，答案是ans = a[L] + a[L+1] + … + a[R] + (R - L + 1)*add[i]，計算次數約為n/t，
?? 情況2，[L, R]跨越了多個塊，在被[L, R]完全包含的那些塊內（設有k個塊），ans += sum[i] + add[i]*len[i]，其中len[i]是第i段的長度，等于n/t，對于不能完全包含的那些碎片，按情況1處理，然后與ans累加，計算次數約為n/t + k，1 ≤ k ≤ t，

long long ask(int L,int R) {
    int p=pos[L],q=pos[R];
    long long ans=0;
    if(p==q){                    //情況1
       for(int i=L;i<=R;i++)     ans += a[i];
       ans+=add[p]*(R-L+1);
    }
    else{//情況2
       for(int i=p+1;i<=q-1;i++)  ans+=sum[i]+add[i]*(ed[i]-st[i]+1);//整塊
       for(int i=L;i<=ed[p];i++)  ans += a[i];   //整塊前面的碎片
       ans += add[p]*(ed[p]-L+1);
       for(int i=st[q];i<=R;i++)  ans += a[i];   //整塊后面的碎片
       ans += add[q]*(R-st[q]+1);
    }
    return ans;
 }

??分塊演算法的實作簡單粗暴，沒有復雜資料結構和復雜邏輯，很容易編碼，
?? 分塊演算法的思想，可以概況為“整塊打包維護，碎片逐個列舉¹”，

3. 復雜度分析

?? 把數列分為t塊，t取何值時有最佳效果？
?? 觀察一次操作的計算次數n/t和n/t + k，其中1 ≤ k ≤ t；當t = 時，有較好的時間復雜度O( )，m次操作的復雜度是$O(m\sqrt{n})$O(mn?)，適合求解m = n = 105規模的問題，或 ≈107的問題，對復雜度的直觀理解，請看圖1，
?? 空間復雜度：需要分配長度為 的陣列st[]、ed[]、sum[]、add[]和長度為n的pos[]、a[]，約3*MAXN，比線段樹的9*MAXN好得多，不過，分塊只能解決m = n = $10^5$105規模的問題，而線段樹是$10^6$106規模的，應用場景不同，直接對比空間無意義，

4. 例題

?? 有些題目用普通的線段樹、樹狀陣列求解很難編碼，而用分塊比較容易，

例題1：區間第k大問題，

教主的魔法 洛谷P2801
題目描述：有N個數，有兩種操作，區間修改（加）、區間詢問，
輸入：第1行有兩個整數n、m，第2行有n個正整數，第3行到第m + 2行，每行是一個操作，有兩種操作：
（1）第一個字母是“M”，后面三個數字L、R、W，表示對閉區間[L, R]內每個數加上W，
（2）第一個字幕是A，后面三個數字L、R、C，詢問閉區間[L, R]內有多少數字大于等于C，
輸出：對每個“A”詢問輸出一行，包含一個整數，表示大于等于C的數有多少個，
資料范圍：n ≤ 1,000,000，m ≤3000，1 ≤ W≤1000，1 ≤ C≤1,000,000,000

題解：
?? 如果用復雜度O(mn)的演算法，不能通過測驗，
?? 詢問區間[L, R]有多少數字大于等于C，等同于問C是區間第幾大，即“區間第k大”問題，標準解法是主席樹，m次操作的復雜度是O(mlogn)，
?? 本題的n較小，用“分塊 + 二分”演算法，復雜度滿足要求，而且代碼很容易寫，容易想到以下分塊操作方法：
?? （1）首先讀取數列a[]，把它分為$\sqrt{n}$n?塊，
?? （2）區間修改，每個塊維護一個add標記，用于記錄塊內的增量W；更新時，區間內的整塊更新add，不完整的碎片，暴力更新其中的每個數，
?? （3）區間查詢，大于等于C的數有多少？如果直接暴力搜每個塊，復雜度為O(n)，不能滿足要求，如果塊中的數是有序的，那么用二分來找大于C的數，復雜度為O(logn)，但是塊內的數是無序的，需要先排序再用二分（可以直接用lower_bound()函式），復雜度O(nlogn + logn)，還不如直接暴力搜，如果能“一次排序，多次使用”，就高效了，
?? 下面是改進后的演算法，
?? （1）在區間操作前，對每個塊的初始值排序，復雜度O(nlogn)，不過，排序會改變原來元素的位置，所以定義一個輔助陣列b[]，它的初值是數列a[]的復制，排序操作在b[]上進行，也就是說，b[]的每個塊內部都是有序的，對b[]的某個塊統計前k個數，就是對a[]的對應塊統計前k個數，
?? （2）區間修改，如果是整塊，維護add標記，不用在b[]上對整塊再排序，因為它仍然保持有序；如果是碎片，暴力修改a[]上對應位置的數，然后把碎片所在的整塊復制到b[]上，對這個塊重新排序，復雜度 = 整塊維護 + 碎片排序 = O($\sqrt{n}+\sqrt{n}log(\sqrt{n})$n?+n?log(n?))，
?? （3）區間查詢，對整塊，因為已經是有序的，直接在b[]的對應整塊上二分查詢；對碎塊，暴力搜a[]上的碎塊，復雜度 = 整塊查詢 + 碎片查詢 = O($\sqrt{n}log(\sqrt{n})+\sqrt{n}$n?log(n?)+n?)，
?? 做m次區間操作，以上三者相加，總復雜度是$O(nlogn)+O(m(\sqrt{n}+\sqrt{n}log(\sqrt{n}))\approx O(m\sqrt{n}log(\sqrt{n}))$O(nlogn)+O(m(n?+n?log(n?))≈O(mn?log(n?))，勉強通過測驗，

例題2：hdu 5057

Argestes and Sequence hdu 5057
Time Limit: 5000/2500 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
題目描述：給定一個序列，有n個非負整數a[1], a[2],…, a[n]，做“單點修改 + 區間查詢”操作，
輸入：第一行是整數T，表示測驗用例數量，對每個測驗，第一行包含兩個數字n、m，第二行是n個非負整數，用空格分割，后面有m行，每行表示一個操作，有兩種操作：
S X Y: 修改操作，把a[x]的值置為y，即a[x] = y；
Q L R D P: 查詢操作，詢問區間[L, R]內有多少個數的第D位是P，
輸出：對每個Q詢問，輸出一行答案，
資料范圍：1≤T≤50，1≤n, m≤100000，0≤a[i]≤$2^{31}$231-1，1≤X≤n，0≤Y≤$2^{31}$231-1，1≤L≤R≤n，1≤D≤10，0≤P≤9

題解：
?? 首先試試分塊，看復雜度是否符合要求，
?? 用分塊編碼非常容易，把陣列分為$\sqrt{n}$n?塊，然后定義block[i][D][P]，表示第i塊第D位是P 的總個數，
?? （1）初始化，讀取陣列a[]的初值，根據a[]計算出block[][][]的初值，復雜度O(n)，
?? （2）修改操作，單點修改a[x]，根據a[x]更新block[][][]，復雜度O(1)，
?? （3）查詢操作，在碎片上，暴力計算[L, R]內的每個a[]，在整塊上，累加所有整塊的block[][][]即可，復雜度 = 整塊的計算 + 碎片的計算 = O($\sqrt{n}$n?) + O($\sqrt{n}$n?) = O($\sqrt{n}$n?)，
?? 總復雜度 = 初始化 + m個操作 = O(n) + O(m$\sqrt{n}$n?)，勉強通過測驗，
?? 此題也可以用樹狀陣列，并且這是一道練習樹狀陣列的好題，樹狀陣列的基礎功能是“單點修改 + 區間查詢”，符合本題的要求，
?? 一個資料最多有D = 10位，每位有P = 0~9這10個數，所以詢問共有D*P = 10*10 = 100種情況，
?? 如果所有的操作只涉及一種情況，用樹狀陣列很容易編程，例如所有的a[i]都只有1位，這1位要么是0，要么是1，然后詢問區間[L, R]內有多少個1，這是最基本的樹狀陣列，
?? 但是，如果100種情況都用樹狀陣列來處理，需要定義的樹狀陣列是int tree[10][10][100000]，需要40M空間，超記憶體，所以必須把tree減少一維，即int tree[10][100000]，此時需要用離線操作的技巧，
?? （1）先讀取并保存所有的修改和查詢操作，
?? （2）“用時間換空間”，分10次處理所有的操作，第1次處理第1位，第2次處理第2位，…等等，每次處理用int tree[10][100000]，分別處理0~9這10個數；這相當于使用了10個樹狀陣列tree[10][100000]，記錄查詢操作的結果，
?? （3）按順序輸出查詢的結果，
?? 計算復雜度是多少？上面的步驟，等于做了10次O(mlogn)的樹狀陣列，注意不是做了100次，請思考原因，樹狀陣列的效率比分塊高很多，不過編碼的難度要高很多倍，

例題3：洛谷 P3203

彈飛綿羊 洛谷 P3203
題目描述：一條直線上擺著n個彈簧，每個彈簧有彈力系數$k_i$ki?，當綿羊到第$i$i個彈簧時，它會被彈到第$i+k_i$i+ki?個位置，若不存在第$i+k_i$i+ki?個彈簧，則綿羊被彈飛，
綿羊想知道當它從第i個彈簧起步時，被彈幾次后會被彈飛，為了使游戲有趣，允許修改某個彈簧的彈力，彈力系數始終為正，
輸入：第一行包含一個整數n，表示地上有n個裝置，編號0~n-1，接下來有n個正整數，依次為n個彈簧的初始彈力系數，第三行有一個正整數m，表示操作次數，接下來m行每行至少有兩個數$i$i，$j$j，
若$i$i=1，你要輸出從j出發被彈幾次后彈飛，
若$i$i=2，則再輸入一個正整數k，表示第j個彈簧的彈力系數被改成k，
輸出：對每個$i$i=1的操作，輸出一行一個整數表示答案，
資料范圍：1≤n≤2×$10^5$105，1≤m≤$10^5$105，

題解：
?? 本題是“單點修改+單點查詢”，如果用暴力法，每次查詢是O(n)的，m次操作，總復雜度O(mn)，超時，本題的標準解法是動態樹LCT，復雜度O(mlogn)，下面用分塊求解，編碼很簡單，復雜度O(m$\sqrt{n}$n?)，勉強通過測驗，
?? 把整個序列分成$\sqrt{n}$n?塊，對于每個點i，維護兩個值：step[i]表示綿羊從第i個點彈出它所在的塊所需要的次數、to[i]表示從第i個點所在的塊彈出后落到其他塊的點，先預處理初始值，復雜度O(n)，
?? 單點查詢，從起點出發，根據to[]找到下一個點（這個點在其他塊里），累加這個程序中所有的step[]即得到總次數，大于n的時候跳出，最多經過$\sqrt{n}$n?個塊，每塊計算一次，復雜度O($\sqrt{n}$n?)，
?? 單點修改，step[i]和to[i]只與i所在的塊有關，與其他塊無關，所以單點修改只需要維護一個塊，復雜度O($\sqrt{n}$n?)，