分块（Sqrt Decomposition）是一种"暴力美学"——将数据分成 √n 大小的块，整块预处理、零散暴力，实现 O(√n) 的查询与修改。莫队算法则是分块思想在离线查询上的优雅应用。
一、分块思想
Mermaid · 渲染中（下方为源码）
graph LR A[数组] --> B[分√n块] B --> C[整块预处理] B --> D[零散暴力] C --> E[O(√n) 查询]
将长度为 n 的数组分成 ⌈n/B⌉ 个块（通常 B = √n）：
数组: [a0, a1, a2, a3, a4, a5, a6, a7, a8]
块: |--- block 0 ---|--- block 1 ---|--- block 2 ---|
B=3 B=3 B=3
- 整块操作：O(1) 利用块的预处理信息
- 零散操作：O(B) 暴力处理两端
二、区间求和 + 单点修改
public class SqrtDecomposition {
private int[] arr;
private long[] blockSum;
private int blockSize;
public SqrtDecomposition(int[] arr) {
this.arr = arr;
int n = arr.length;
blockSize = (int) Math.sqrt(n) + 1;
blockSum = new long[(n + blockSize - 1) / blockSize];
for (int i = 0; i < n; i++) {
blockSum[i / blockSize] += arr[i];
}
}
// 单点修改 O(1)
public void update(int index, int val) {
int block = index / blockSize;
blockSum[block] += val - arr[index];
arr[index] = val;
}
// 区间求和 O(√n)
public long query(int l, int r) {
long sum = 0;
int blockL = l / blockSize;
int blockR = r / blockSize;
if (blockL == blockR) {
// 同一块：暴力
for (int i = l; i <= r; i++) sum += arr[i];
} else {
// 左零散
for (int i = l; i < (blockL + 1) * blockSize; i++) sum += arr[i];
// 中间整块
for (int b = blockL + 1; b < blockR; b++) sum += blockSum[b];
// 右零散
for (int i = blockR * blockSize; i <= r; i++) sum += arr[i];
}
return sum;
}
}