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

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

01

分塊概念

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

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

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

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

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

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

02

分塊算法

塊操作的基本要素有：

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

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

（3）塊的左右邊界。定義數(shù)組st[]、ed[]，用st[i]、ed[i]表示塊i的第一個(gè)和最后一個(gè)元素的位置。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）每個(gè)元素所屬的塊。定義pos[]，pos[i]表示第i個(gè)元素所在的塊，pos[i]=(i-1)/block + 1。

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

展開(kāi)全文

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

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ū)間問(wèn)題很方便，下面以“區(qū)間修改+區(qū)間查詢”（洛谷P3372）為例。

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

（1）定義數(shù)組a[]存儲(chǔ)數(shù)據(jù)，共n個(gè)元素，讀取初值，存儲(chǔ)在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。

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

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

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

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

總結(jié)兩種情況，處理碎塊時(shí)，只更新sum[i]，不更新add[i]；處理整塊時(shí)，只更新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個(gè)。計(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)每個(gè)數(shù)的和。

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

情況2，[L, R]跨越了多個(gè)塊。在被[L, R]完全包含的那些塊內(nèi)（設(shè)有k個(gè)塊），ans += sum[i] + add[i]*len[i]，其中l(wèi)en[i]是第i段的長(zhǎng)度，等于n/t。對(duì)于不能完全包含的那些碎片，按情況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)簡(jiǎn)單粗暴，沒(méi)有復(fù)雜數(shù)據(jù)結(jié)構(gòu)和復(fù)雜邏輯，很容易編碼。

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

03

復(fù)雜度分析

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

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

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

04

例題

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

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

教主的魔法洛谷P2801

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

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

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

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

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

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

題解：

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

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

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

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

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

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

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

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

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

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

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

例題2：hdu 5057

Argestes and Sequencehdu 5057

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

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

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

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

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

輸出：對(duì)每個(gè)Q詢問(wèn)，輸出一行答案。

數(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 的總個(gè)數(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)的每個(gè)a[]。在整塊上，累加所有整塊的block[][][]即可。復(fù)雜度 = 整塊的計(jì)算 + 碎片的計(jì)算 = O(√n) + O(√n) = O(√n)。

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

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

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

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

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

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

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

例題3：洛谷 P3203

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

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

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

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

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

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

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

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

題解：

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

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

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

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

05

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