分塊
是一種思想，把一個整體劃分為若干個小塊，對整塊整體處理，零散塊單獨處理。本文主要介紹
塊狀陣列
——利用分塊思想處理區間問題的一種資料結構。
塊狀陣列把一個長度為
的陣列劃分為
塊，每塊長度為
。對於一次區間操作，對區間內部的整塊進行整體的操作，對區間邊緣的零散塊單獨暴力處理。（所以分塊被稱為“優雅的暴力”）
這裡，塊數既不能太少也不能太多。如果太少，區間中整塊的數量會很少，我們要花費大量時間處理零散塊；如果太多，又會讓塊的長度太短，失去整體處理的意義。一般來說，我們取塊數為
，這樣在最壞情況下，我們要處理接近
個整塊，還要對長度為
的零散塊單獨處理，總時間複雜度為
。這是一種
根號演算法
。
顯然，分塊的時間複雜度比不上線段樹和樹狀陣列這些
對數級演算法
。但由此換來的，是更高的靈活性。與線段樹不同，塊狀陣列並不要求所維護資訊滿足結合律，也不需要一層層地傳遞標記。但它們又有相似之處，線段樹是一棵高度約為
的樹，而塊狀陣列則可被看成一棵高度為3的樹：
只不過，塊狀陣列最頂層的資訊不用維護。
預處理
具體地使用塊狀陣列，我們要先劃定出每個塊所佔據的範圍：
int
sq
=
sqrt
（
n
）；
for
（
int
i
=
1
；
i
<=
sq
；
++
i
）
{
st
［
i
］
=
n
/
sq
*
（
i
-
1
）
+
1
；
// st［i］表示i號塊的第一個元素的下標
ed
［
i
］
=
n
/
sq
*
i
；
// ed［i］表示i號塊的最後一個元素的下標
}
但是，陣列的長度並不一定是一個完全平方數，所以這樣下來很可能會漏掉一小塊，我們把它們納入最後一塊中：
ed
［
sq
］
=
n
；
然後，我們為每個元素確定它所歸屬的塊：
for
（
int
i
=
1
；
i
<=
sq
；
++
i
）
for
（
int
j
=
st
［
i
］；
j
<=
ed
［
i
］；
++
j
）
bel
［
j
］
=
i
；
// 表示j號元素歸屬於i塊
最後，如果必要，我們再預處理每個塊的大小：
for
（
int
i
=
1
；
i
<=
sq
；
++
i
）
size
［
i
］
=
ed
［
i
］
-
st
［
i
］
+
1
；
好了，準備工作做完了，後面的事情就很簡單了。分塊的程式碼量也許不比線段樹小多少，但看起來要好理解很多，我們先來搞線段樹模板題。
（洛谷P3372 【模板】線段樹1）
題目描述
如題，已知一個數列，你需要進行下面兩種操作：
將某區間每一個數加上 k。
求出某區間每一個數的和。
輸入格式
第一行包含兩個整數 n， m，分別表示該數列數字的個數和操作的總個數。
第二行包含 n 個用空格分隔的整數，其中第 i 個數字表示數列第 i 項的初始值。
接下來 m 行每行包含 3 或 4 個整數，表示一個操作，具體如下：
1 x y k
：將區間 ［x， y］ 內每個數加上 k 。
2 x y
：輸出區間 ［x， y］ 內每個數的和。
這個題資料範圍只有
，可以用分塊。我們用一個
sum
陣列來記錄每一塊的和，
mark
陣列來做標記（注意這兩者要分開，因為處理零散塊時也要用到標記）。
讀入和預處理資料
for （int i = 1； i <= n； ++i）
A［i］ = read（）；
for （int i = 1； i <= sq； ++i）
for （int j = st［i］； j <= ed［i］； ++j）
sum［i］ += A［j］；
sum［i］
儲存第
i
個塊的和。
區間修改
首先是區間修改，當x與y在同一塊內時，直接暴力修改原陣列和
sum
陣列：
if
（
bel
［
x
］
==
bel
［
y
］）
for
（
int
i
=
x
；
i
<=
y
；
++
i
）
{
A
［
i
］
+=
k
；
sum
［
bel
［
i
］］
+=
k
；
}
否則，先暴力修改左右兩邊的零散區間：
for
（
int
i
=
x
；
i
<=
ed
［
bel
［
x
］］；
++
i
）
{
A
［
i
］
+=
k
；
sum
［
bel
［
i
］］
+=
k
；
}
for
（
int
i
=
st
［
bel
［
y
］］；
i
<=
y
；
++
i
）
{
A
［
i
］
+=
k
；
sum
［
bel
［
i
］］
+=
k
；
}
然後對中間的整塊打上標記：
for
（
int
i
=
bel
［
x
］
+
1
；
i
<
bel
［
y
］；
++
i
）
mark
［
i
］
+=
k
；
區間查詢
同樣地，如果左右兩邊在同一塊，直接暴力計算區間和。
if
（
bel
［
x
］
==
bel
［
y
］）
for
（
int
i
=
x
；
i
<=
y
；
++
i
）
s
+=
A
［
i
］
+
mark
［
bel
［
i
］］；
// 注意要加上標記
否則，暴力計算零碎塊：
for
（
int
i
=
x
；
i
<=
ed
［
bel
［
x
］］；
++
i
）
s
+=
A
［
i
］
+
mark
［
bel
［
i
］］；
for
（
int
i
=
st
［
bel
［
y
］］；
i
<=
y
；
++
i
）
s
+=
A
［
i
］
+
mark
［
bel
［
i
］］；
再處理整塊：
for
（
int
i
=
bel
［
x
］
+
1
；
i
<
bel
［
y
］；
++
i
）
s
+=
sum
［
i
］
+
mark
［
i
］
*
size
［
i
］；
// 注意標記要乘上塊長
於是我們用分塊A掉了線段樹的模板題（線段樹：喵喵喵？）。洛谷上跑得還挺快，比較資料範圍很小。
上面用分塊解決問題的思路非常簡單。然而，如果總是這麼簡單就好了……實際上，分塊的題目可以出得很靈活、很難。我們來看“相對”簡單的一道：
（洛谷P2801 教主的魔法）
題目描述
教主最近學會了一種神奇的魔法，能夠使人長高。於是他準備演示給XMYZ資訊組每個英雄看。於是N個英雄們又一次聚集在了一起，這次他們排成了一列，被編號為1、2、……、N。
每個人的身高一開始都是不超過1000的正整數。教主的魔法每次可以把閉區間［L， R］（1≤L≤R≤N）內的英雄的身高全部加上一個整數W。（雖然L=R時並不符合區間的書寫規範，但我們可以認為是單獨增加第L（R）個英雄的身高）
CYZ、光哥和ZJQ等人不信教主的邪，於是他們有時候會問WD閉區間 ［L， R］ 內有多少英雄身高大於等於C，以驗證教主的魔法是否真的有效。
WD巨懶，於是他把這個回答的任務交給了你。
輸入格式
第1行為兩個整數N、Q。Q為問題數與教主的施法數總和。
第2行有N個正整數，第i個數代表第i個英雄的身高。
第3到第Q+2行每行有一個操作：
（1） 若第一個字母為“M”，則緊接著有三個數字L、R、W。表示對閉區間 ［L， R］ 內所有英雄的身高加上W。
（2） 若第一個字母為“A”，則緊接著有三個數字L、R、C。詢問閉區間 ［L， R］ 內有多少英雄的身高大於等於C。
輸出格式
對每個“A”詢問輸出一行，僅含一個整數，表示閉區間 ［L， R］ 內身高大於等於C的英雄數。
資料範圍
對30%的資料，N≤1000，Q≤1000。
對100%的資料，N≤1000000，Q≤3000，1≤W≤1000，1≤C≤1，000，000，000。
區間加，詢問區間大於等於C的元素個數。這個用線段樹顯然不方便（總不可能對每個C開一棵線段樹吧……）。發現雖然N最大為
，但Q較小，分塊可行。
零散塊暴力處理起來顯然很容易，但如何對整塊整體處理呢？實際上我們可以維護整塊
排序
後的陣列，然後對整塊進行詢問時直接
二分查詢
。
注意，我們每次對零散塊單獨修改時，都需要
更新
排序後的陣列，這聽起來很暴力，但由於每個塊相對較少，也可以接受。總時間複雜度
。
主要程式碼如下：
/* 。。。 */
const
int
MAXN
=
1000005
，
SQ
=
1005
；
int
st
［
SQ
］，
ed
［
SQ
］，
size
［
SQ
］，
bel
［
MAXN
］；
void
init_block
（
int
n
）
// 初始化
{
int
sq
=
sqrt
（
n
）；
for
（
int
i
=
1
；
i
<=
sq
；
++
i
）
{
st
［
i
］
=
n
/
sq
*
（
i
-
1
）
+
1
；
ed
［
i
］
=
n
/
sq
*
i
；
}
ed
［
sq
］
=
n
；
for
（
int
i
=
1
；
i
<=
sq
；
++
i
）
for
（
int
j
=
st
［
i
］；
j
<=
ed
［
i
］；
++
j
）
bel
［
j
］
=
i
；
for
（
int
i
=
1
；
i
<=
sq
；
++
i
）
size
［
i
］
=
ed
［
i
］
-
st
［
i
］
+
1
；
}
int
A
［
MAXN
］，
mark
［
SQ
］；
vector
<
int
>
v
［
SQ
］；
// 這裡用vector存排序後的陣列
void
update
（
int
b
）
// 更新排序後的陣列
{
for
（
int
i
=
0
；
i
<=
size
［
b
］；
++
i
）
v
［
b
］［
i
］
=
A
［
st
［
b
］
+
i
］；
sort
（
v
［
b
］。
begin
（），
v
［
b
］。
end
（））；
}
int
main
（）
{
int
n
=
read
（），
m
=
read
（）；
int
sq
=
sqrt
（
n
）；
init_block
（
n
）；
for
（
int
i
=
1
；
i
<=
n
；
++
i
）
A
［
i
］
=
read
（）；
for
（
int
i
=
1
；
i
<=
sq
；
++
i
）
for
（
int
j
=
st
［
i
］；
j
<=
ed
［
i
］；
++
j
）
v
［
i
］。
push_back
（
A
［
j
］）；
for
（
int
i
=
1
；
i
<=
sq
；
++
i
）
sort
（
v
［
i
］。
begin
（），
v
［
i
］。
end
（））；
while
（
m
——
）
{
char
o
；
scanf
（
“ %c”
，
&
o
）；
int
l
=
read
（），
r
=
read
（），
k
=
read
（）；
if
（
o
==
‘M’
）
{
if
（
bel
［
l
］
==
bel
［
r
］）
// 如果同屬一塊直接暴力
{
for
（
int
i
=
l
；
i
<=
r
；
++
i
）
A
［
i
］
+=
k
；
update
（
bel
［
l
］）；
continue
；
}
for
（
int
i
=
l
；
i
<=
ed
［
bel
［
l
］］；
++
i
）
// 對零散塊暴力處理
A
［
i
］
+=
k
；
for
（
int
i
=
st
［
bel
［
r
］］；
i
<=
r
；
++
i
）
A
［
i
］
+=
k
；
update
（
bel
［
l
］）；
update
（
bel
［
r
］）；
for
（
int
i
=
bel
［
l
］
+
1
；
i
<
bel
［
r
］；
++
i
）
// 打上標記
mark
［
i
］
+=
k
；
}
else
{
int
tot
=
0
；
if
（
bel
［
l
］
==
bel
［
r
］）
{
for
（
int
i
=
l
；
i
<=
r
；
++
i
）
if
（
A
［
i
］
+
mark
［
bel
［
l
］］
>=
k
）
tot
++
；
printf
（
“%d
\n
”
，
tot
）；
continue
；
}
for
（
int
i
=
l
；
i
<=
ed
［
bel
［
l
］］；
++
i
）
if
（
A
［
i
］
+
mark
［
bel
［
l
］］
>=
k
）
tot
++
；
for
（
int
i
=
st
［
bel
［
r
］］；
i
<=
r
；
++
i
）
if
（
A
［
i
］
+
mark
［
bel
［
r
］］
>=
k
）
tot
++
；
// 二分查詢k-mark［i］的位置，因為整塊都加上了mark［i］其實就相當於k減去mark［i］
for
（
int
i
=
bel
［
l
］
+
1
；
i
<
bel
［
r
］；
++
i
）
tot
+=
v
［
i
］。
end
（）
-
lower_bound
（
v
［
i
］。
begin
（），
v
［
i
］。
end
（），
k
-
mark
［
i
］）；
printf
（
“%d
\n
”
，
tot
）；
}
}
return
0
；
}
這篇筆記先寫到這裡，關於使用塊狀陣列的更困難的題目，以及分塊思想的其他應用，以後有機會再寫吧。
