分块
简单理解一下，分块就是优雅的暴力。
分块的分类
- 静态分块（只做查询，预处理）：
静态分块指的是放一些关键点，预处理关键点到关键点的信息，来加速查询的，不能支持修改。
目前认为，如果可以离线，静态分块是莫队算法的子集。
- 动态分块（支持修改和查询）：
动态分块指的是把序列分为一些块，每块维护一些信息，可以支持修改。
分块基础
对于一个长度为 \(n\) 的序列，我们可以分为一些块，每块维护一些信息。
我们把每次操作完整覆盖的块定义为“完整的块”。
把每次操作不完整覆盖的块定义为“不完整的块”。
每次操作最多经过 \(O(\sqrt{n})\) 个块，以及 \(O(1)\) 个零散块。
所以我们可以 \(O(1)\) 维护整块信息，\(O(\sqrt{n})\) 查询零散块信息。
这样就达到了 \(O(m\sqrt{n})\) 的复杂度。
分块的本质
一个度为 \(\sqrt{n}\)，只有 \(3\) 层的树。
每次修改只需要更新 \(\sqrt{n}\) 个 size 为 \(1\) 的节点，以及 \(2\) 个 size 为 \(\sqrt{n}\) 的节点。
注意到我们不用维护那个 size 为 \(n\) 的根节点的信息。
建立分块序列
\(B\) 表示每一块有多大，\(num\) 表示一共有多少块，\(belong_i\) 表示原序列中的第 \(i\) 个元素属于哪一块，\(l_i\) 和 \(r_i\) 表示第 \(i\) 块的左右边界。
B = sqrt(n);
num = n / B + (n % B != 0);
for (int i = 1; i <= n; i ++ ) {
belong[i] = (i - 1) / B + 1;
l[i] = (i - 1) * B + 1;
r[i] = i * B;
}
r[num] = n;
区间修改
for (int i = l; i <= min(r, belong[l] * B); i ++ ) a[i] += c;
if (belong[l] != belong[r]) for (int i = (belong[r] - 1) * B + 1; i <= r; i ++ ) a[i] += c;
for (int i = belong[l] + 1; i < belong[r]; i ++ ) add[i] += c;
单点查询
a[i] + add[belong[i]];
区间查询
for (int i = l; i <= min(r, belong[l] * B); i ++ ) res += a[i] + add[belong[l]];
if (belong[l] != belong[r]) for (int i = (belong[r] - 1) * B + 1; i <= r; i ++ ) res += a[i] + add[belong[r]];
for (int i = belong[l] + 1; i < belong[r]; i ++ ) res += sum[i] + add[i] * B;