本篇內(nèi)容包括了分塊算法的思想的介紹、分塊算法復(fù)雜度的分析以及相關(guān)例題。

*本文內(nèi)容由羅勇軍老師提供。

01

分塊概念

回顧“區(qū)間”問題，前面給出了暴力法、樹狀數(shù)組、線段樹等算法。給定一個保存n個數(shù)據(jù)的數(shù)列，做m次“區(qū)間修改”和“區(qū)間查詢”，每次操作只涉及到部分區(qū)間。暴力法只是簡單地從整體上做修改和查詢，復(fù)雜度O(mn)，很低效。樹狀數(shù)組和線段樹都用到了二分的思想，以O(shè)(logn)的復(fù)雜度組織數(shù)據(jù)結(jié)構(gòu)，每次只處理涉及到的區(qū)間，從而實(shí)現(xiàn)了O(mlogn)的高效的復(fù)雜度。

雖然暴力法只能解決小規(guī)模的問題，但是它的代碼非常簡單。

有一種代碼比樹狀數(shù)組、線段樹簡單，效率比暴力法高的算法，稱為“ 分塊”，它能以O(shè)(m√n)的復(fù)雜度解決“區(qū)間修改+區(qū)間查詢”問題。簡單地說，分塊是用線段樹的“分區(qū)”思想改良的暴力法；它把數(shù)列分成很多“塊”，對涉及到的塊做整體性的維護(hù)操作（類似于線段樹的lazy-tag），而不是像普通暴力法那樣處理整個數(shù)列，從而提高了效率。

用一個長度為n的數(shù)組來存儲n個數(shù)據(jù)，把它分為t塊，每塊長度為n/t。下圖(1)是一個有10個元素的數(shù)組，共分成4塊，前3塊每塊3個元素，最后一塊1個元素。

▍ 圖1 (1)分塊 ????? (2)與線段樹的結(jié)構(gòu)對比

對比塊狀數(shù)組與線段樹，線段樹是一棵高度為logn的樹，塊狀數(shù)組可以看成一棵高度為3的樹，見圖(2)。從圖(2)可知，在線段樹上做一次操作是O(logn)的，因?yàn)樗衛(wèi)ogn層；分塊是O(n/t)的，因?yàn)樗褦?shù)據(jù)分成了t塊，處理一塊的時間是n/t的。下面介紹分塊算法，并詳細(xì)說明復(fù)雜度。

02

分塊算法

塊操作的基本要素有：

（1）塊的大小。用block表示。

（2）塊的數(shù)量。用t表示。

（3）塊的左右邊界。定義數(shù)組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。

具體內(nèi)容見下面的代碼。其中每塊的大小block的值等于√n取整，后面的“復(fù)雜度分析”會說明原因。如果√n的結(jié)果不是整數(shù)，那么最后要加上一小塊，代碼中重要的內(nèi)容是處理這個問題。

展開全文

intblock = sqrt(n); //塊的大?。好繅K有block個元素。

intt = n/block; //塊的數(shù)量：共分為t塊

if(n % block) t++; //sqrt(n)的結(jié)果不是整數(shù)，最后加一小塊

for( inti= 1; i=t; i++){ //遍歷塊

st[i] = (i -1)*block+ 1;

ed[i] = i*block;

}

ed[t] = n; //sqrt(n)的結(jié)果不是整數(shù)，最后一塊較小

for( inti= 1; i=n; i++) //遍歷所有元素的位置

pos[i]=(i -1)/block + 1;

用分塊解決區(qū)間問題很方便，下面以“區(qū)間修改+區(qū)間查詢”（洛谷P3372）為例。

首先定義區(qū)間有關(guān)的輔助數(shù)組：

（1）定義數(shù)組a[]存儲數(shù)據(jù)，共n個元素，讀取初值，存儲在a[1]、a[2]、…、a[n]中。

（2）定義sum[]，sum[i]為第i塊的區(qū)間和，并預(yù)處理出初值。

for( inti= 1; i=t; i++) //遍歷所有的塊

for( intj=st[i]; j=ed[i];j++) //遍歷塊i內(nèi)的所有元素

sum[i] += a[j];

（3）定義add[]，add[i]為第i塊的增量標(biāo)記，初始值為0。

然后對數(shù)列a[]做“區(qū)間修改+區(qū)間查詢”操作：

1. 區(qū)間修改：將區(qū)間[L, R]內(nèi)每個數(shù)加上d。

情況1，[L, R]在某個i塊之內(nèi)，即[L, R]是一個“碎片”。把a(bǔ)[L]、a[L+1]、…、a[R]逐個加上d，更新sum[i] = sum[i] + d*(R - L + 1)。計(jì)算次數(shù)約為n/t。

情況2，[L, R]跨越了多個塊。在被[L, R]完全包含的那些整塊內(nèi)（設(shè)有k個塊），更新add[i] = add[i] + d。對于不能完全包含的那些碎片（它們在k個整塊的兩頭），按情況1處理。情況2的計(jì)算次數(shù)約為n/t + k，1 ≤ k ≤ t。

總結(jié)兩種情況，處理碎塊時，只更新sum[i]，不更新add[i]；處理整塊時，只更新add[i]，不更新sum[i]。

voidchange( intL, intR, intd ) {

intp = pos[L], q = pos[R];

if(p==q){ //情況1，計(jì)算次數(shù)是n/t

for( inti=L;i=R;i++) a[i]+=d;

sum[p]+=d*(R-L+ 1);

}

else{ //情況2

for( inti=p+ 1;i=q -1;i++) add[i]+=d; //整塊，有m=(q-1)-(p+1)+1個。計(jì)算m次

for( inti=L;i=ed[p];i++) a[i]+=d; //整塊前面的碎片。計(jì)算n/t次

sum[p]+=d*(ed[p]-L+ 1);

for( inti=st[q];i=R;i++) a[i]+=d; //整塊后面的碎片。計(jì)算n/t次

sum[q]+=d*(R-st[q]+ 1);

}

}

2. 區(qū)間查詢：輸出區(qū)間[L, R]內(nèi)每個數(shù)的和。

情況1，[L, R]在某個i塊之內(nèi)。暴力加每個數(shù)，最后加上add[i]，答案是ans = a[L] + a[L+1] + … + a[R] + (R - L + 1)*add[i]。計(jì)算次數(shù)約為n/t。

情況2，[L, R]跨越了多個塊。在被[L, R]完全包含的那些塊內(nèi)（設(shè)有k個塊），ans += sum[i] + add[i]*len[i]，其中l(wèi)en[i]是第i段的長度，等于n/t。對于不能完全包含的那些碎片，按情況1處理，然后與ans累加。計(jì)算次數(shù)約為n/t + k，1 ≤ k ≤ t。

longlongask( intL, intR ) {

intp=pos[L],q=pos[R];

longlongans= 0;

if(p==q){ //情況1

for( inti=L;i=R;i++) ans += a[i];

ans+= add[p]*(R-L+ 1);

}

else{ //情況2

for( inti=p+ 1;i=q -1;i++) ans+=sum[i]+ add[i]*(ed[i]-st[i]+ 1); //整塊

for( inti=L;i=ed[p];i++) ans += a[i]; //整塊前面的碎片

ans += add[p]*(ed[p]-L+ 1);

for( inti=st[q];i=R;i++) ans += a[i]; //整塊后面的碎片

ans += add[q]*(R-st[q]+ 1);

}

returnans;

}

分塊算法的實(shí)現(xiàn)簡單粗暴，沒有復(fù)雜數(shù)據(jù)結(jié)構(gòu)和復(fù)雜邏輯，很容易編碼。

分塊算法的思想，可以概況為 “整塊打包維護(hù)，碎片逐個枚舉”。

03

復(fù)雜度分析

把數(shù)列分為t塊，t取何值時有最佳效果？

觀察一次操作的計(jì)算次數(shù)n/t和n/t+k，其中1≤k≤t；當(dāng)t=√n 時，有較好的時間復(fù)雜度O(√n)。m次操作的復(fù)雜度是O(m√n)，適合求解m=n=10 5 規(guī)模的問題，或 O(m√n)≈10 7 的問題。對復(fù)雜度的直觀理解，請看圖。

空間復(fù)雜度：需要分配長度為 的數(shù)組st[]、ed[]、sum[]、add[]和長度為n的pos[]、a[]，約3*MAXN，比線段樹的9*MAXN好得多。不過，分塊只能解決m = n = 10 5 規(guī)模的問題，而線段樹是10 6 規(guī)模的，應(yīng)用場景不同，直接對比空間無意義。

04

例題

有些題目用普通的線段樹、樹狀數(shù)組求解很難編碼，而用分塊比較容易。

例題1：區(qū)間第k大問題

教主的魔法洛谷P2801

題目描述：有N個數(shù)，有兩種操作，區(qū)間修改（加）、區(qū)間詢問。

輸入：第1行有兩個整數(shù)n、m。第2行有n個正整數(shù)。第3行到第m + 2行，每行是一個操作，有兩種操作：

（1）第一個字母是“M”，后面三個數(shù)字L、R、W，表示對閉區(qū)間[L, R]內(nèi)每個數(shù)加上W。

（2）第一個字幕是A，后面三個數(shù)字L、R、C，詢問閉區(qū)間[L, R]內(nèi)有多少數(shù)字大于等于C。

輸出：對每個“A”詢問輸出一行，包含一個整數(shù)，表示大于等于C的數(shù)有多少個。

數(shù)據(jù)范圍：n ≤ 1,000,000，m ≤3000，1 ≤ W≤1000，1 ≤ C≤1,000,000,000

題解：

如果用復(fù)雜度O(mn)的算法，不能通過測試。

詢問區(qū)間[L, R]有多少數(shù)字大于等于C，等同于問C是區(qū)間第幾大，即“區(qū)間第k大”問題，標(biāo)準(zhǔn)解法是主席樹，m次操作的復(fù)雜度是O(mlogn)。

本題的n較小，用“分塊 + 二分”算法，復(fù)雜度滿足要求，而且代碼很容易寫。容易想到以下分塊操作方法：

（1）首先讀取數(shù)列a[]，把它分為√n塊。

（2）區(qū)間修改。每個塊維護(hù)一個add標(biāo)記，用于記錄塊內(nèi)的增量W；更新時，區(qū)間內(nèi)的整塊更新add，不完整的碎片，暴力更新其中的每個數(shù)。

（3）區(qū)間查詢。大于等于C的數(shù)有多少？如果直接暴力搜每個塊，復(fù)雜度為O(n)，不能滿足要求。如果塊中的數(shù)是有序的，那么用二分來找大于C的數(shù)，復(fù)雜度為O(logn)。但是塊內(nèi)的數(shù)是無序的，需要先排序再用二分（可以直接用lower_bound函數(shù)），復(fù)雜度O(nlogn + logn)，還不如直接暴力搜。如果能“一次排序，多次使用”，就高效了。

下面是改進(jìn)后的算法。

（1）在區(qū)間操作前，對每個塊的初始值排序，復(fù)雜度O(nlogn)。不過，排序會改變原來元素的位置，所以定義一個輔助數(shù)組b[]，它的初值是數(shù)列a[]的復(fù)制，排序操作在b[]上進(jìn)行。也就是說，b[]的每個塊內(nèi)部都是有序的，對b[]的某個塊統(tǒng)計(jì)前k個數(shù)，就是對a[]的對應(yīng)塊統(tǒng)計(jì)前k個數(shù)。

（2）區(qū)間修改。如果是整塊，維護(hù)add標(biāo)記，不用在b[]上對整塊再排序，因?yàn)樗匀槐３钟行颍蝗绻撬槠?，暴力修改a[]上對應(yīng)位置的數(shù)，然后把碎片所在的整塊復(fù)制到b[]上，對這個塊重新排序。復(fù)雜度 = 整塊維護(hù) + 碎片排序 = O(√n + √n l o g (√ n )）。

（3）區(qū)間查詢。對整塊，因?yàn)橐呀?jīng)是有序的，直接在b[]的對應(yīng)整塊上二分查詢；對碎塊，暴力搜a(bǔ)[]上的碎塊。復(fù)雜度 = 整塊查詢 + 碎片查詢 = O(√nlog(√n)+√n)。

做m次區(qū)間操作，以上三者相加，總復(fù)雜度是O(nlogn)+O(m(√n+√nlog(√n))≈O(m√nlog(√n))。勉強(qiáng)通過測試。

例題2：hdu 5057

Argestes and Sequencehdu 5057

Time Limit: 5000/2500 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

題目描述：給定一個序列，有n個非負(fù)整數(shù)a[1], a[2],…, a[n]。做“單點(diǎn)修改 + 區(qū)間查詢”操作。

輸入：第一行是整數(shù)T，表示測試用例數(shù)量。對每個測試，第一行包含兩個數(shù)字n、m。第二行是n個非負(fù)整數(shù)，用空格分割，后面有m行，每行表示一個操作，有兩種操作：

S X Y: 修改操作，把a(bǔ)[x]的值置為y，即a[x] = y；

Q L R D P: 查詢操作，詢問區(qū)間[L, R]內(nèi)有多少個數(shù)的第D位是P。

輸出：對每個Q詢問，輸出一行答案。

數(shù)據(jù)范圍：1≤T≤50，1≤n, m≤100000，0≤a[i]≤2 31 -1，1≤L≤R≤n，1≤D≤10，0≤P≤9

題解：

首先試試分塊，看復(fù)雜度是否符合要求。

用分塊編碼非常容易。把數(shù)組分為√n塊，然后定義block[i][D][P]，表示第i塊第D位是P 的總個數(shù)。

（1）初始化。讀取數(shù)組a[]的初值，根據(jù)a[]計(jì)算出block[][][]的初值。復(fù)雜度O(n)。

（2）修改操作。單點(diǎn)修改a[x]，根據(jù)a[x]更新block[][][]。復(fù)雜度O(1)。

（3）查詢操作。在碎片上，暴力計(jì)算[L, R]內(nèi)的每個a[]。在整塊上，累加所有整塊的block[][][]即可。復(fù)雜度 = 整塊的計(jì)算 + 碎片的計(jì)算 = O(√n) + O(√n) = O(√n)。

總復(fù)雜度 = 初始化 + m個操作 = O(n) + O(m√n)，勉強(qiáng)通過測試。

此題也可以用樹狀數(shù)組，并且這是一道練習(xí)樹狀數(shù)組的好題。樹狀數(shù)組的基礎(chǔ)功能是“單點(diǎn)修改 + 區(qū)間查詢”，符合本題的要求。

一個數(shù)據(jù)最多有D = 10位，每位有P = 0~9這10個數(shù)，所以詢問共有D*P = 10*10 = 100種情況。

如果所有的操作只涉及一種情況，用樹狀數(shù)組很容易編程。例如所有的a[i]都只有1位，這1位要么是0，要么是1，然后詢問區(qū)間[L, R]內(nèi)有多少個1。這是最基本的樹狀數(shù)組。

（1）先讀取并保存所有的修改和查詢操作。

（3）按順序輸出查詢的結(jié)果。

計(jì)算復(fù)雜度是多少？上面的步驟，等于做了10次O(mlogn)的樹狀數(shù)組，注意不是做了100次，請思考原因。樹狀數(shù)組的效率比分塊高很多，不過編碼的難度要高很多倍。

例題3：洛谷 P3203

題目描述：一條直線上擺著n個彈簧，每個彈簧有彈力系數(shù)k i ，當(dāng)綿羊到第i個彈簧時，它會被彈到第i+k i 個位置，若不存在第i+k i 個彈簧，則綿羊被彈飛。

綿羊想知道當(dāng)它從第i個彈簧起步時，被彈幾次后會被彈飛。為了使游戲有趣，允許修改某個彈簧的彈力。彈力系數(shù)始終為正。

輸入：第一行包含一個整數(shù)n，表示地上有n個裝置，編號0~n-1。接下來有n個正整數(shù)，依次為n個彈簧的初始彈力系數(shù)。第三行有一個正整數(shù)m，表示操作次數(shù)。

接下來m行每行至少有兩個數(shù)i，j。

若i=1，你要輸出從j出發(fā)被彈幾次后彈飛。

若i=2，則再輸入一個正整數(shù)k，表示第j個彈簧的彈力系數(shù)被改成k。

輸出：對每個i=1的操作，輸出一行一個整數(shù)表示答案。

數(shù)據(jù)范圍：1≤n≤2×10 5 ，1≤m≤10 5 。

題解：

本題是“單點(diǎn)修改+單點(diǎn)查詢”，如果用暴力法，每次查詢是O(n)的，m次操作，總復(fù)雜度O(mn)，超時。本題的標(biāo)準(zhǔn)解法是動態(tài)樹LCT，復(fù)雜度O(mlogn)。下面用分塊求解，編碼很簡單，復(fù)雜度O(m√n)，勉強(qiáng)通過測試。

把整個序列分成√n塊，對于每個點(diǎn)i，維護(hù)兩個值：step[i]表示綿羊從第i個點(diǎn)彈出它所在的塊所需要的次數(shù)、to[i]表示從第i個點(diǎn)所在的塊彈出后落到其他塊的點(diǎn)。先預(yù)處理初始值，復(fù)雜度O(n)。

單點(diǎn)查詢。從起點(diǎn)出發(fā)，根據(jù)to[]找到下一個點(diǎn)（這個點(diǎn)在其他塊里），累加這個過程中所有的step[]即得到總次數(shù)，大于n的時候跳出。最多經(jīng)過√n個塊，每塊計(jì)算一次，復(fù)雜度O(√n)。

單點(diǎn)修改。step[i]和to[i]只與i所在的塊有關(guān)，與其他塊無關(guān)，所以單點(diǎn)修改只需要維護(hù)一個塊，復(fù)雜度O(√n)。

05

實(shí)現(xiàn)代碼