最近写了几个分块，顺便做一下笔记。
什么是分块
分块是一种数据结构。。
有许多数据结构都是 \(\mathrm{log}\) 数据结构，比如线段树，树状数组等等。他们复杂度优秀，但是都是树形结构，有较大的思维难度和局限性。那么有没有什么复杂度一般，但是非树形的数据结构呢？
有的，就是分块。
分块的思路是把数据分成一个个的小块。设每块长为 \(\text{S}\)。举个栗子：
1, 1, 4, 5, 1, 4 (S = 2)
那么我们就可以把他分成
1, 1 | 4, 5 | 1, 4
我们成功把他分成了三个小块。
对于每个询问 \(\mathrm{[l, r]}\)，它会跨越许多小块和整块。比如对于刚才那个数据：
1, 1 | 4, 5 | 1, 4 (l = 2, r = 5, S = 2)
| |
l -------- r
l, r 跨越了第一块的后半个，第二块和第三块的前半个。
对于整块，我们一般可以用打懒标记之类的方法来搞，一共有 \(\dfrac{n}{S}\) 个整块，所以复杂度最坏也是 \(\mathrm{O(\dfrac{n}{S})}\)。对于散块来说，最多会有一左一右两个散块，长度最多为 \(\mathrm{2S}\)，对他们进行暴力操作，复杂度最坏为 \(\mathrm{O(S)}\)。考虑常数，总复杂度为 \(\mathrm{O(2S + \dfrac{n}{S})}\)。（虽然 \(O\) 里面不应该加常数）。根据均值不等式，当 \(\mathrm{S = \dfrac{\sqrt{2}}{2} \sqrt{n}}\)。通常我们取 \(S = \sqrt{n}\)，单次操作复杂度稳定在 \(\mathrm{O(\sqrt{n})}\) 级别。
分块怎么写
首先先说一下分块的几个重要操作：
- 定位操作。\(\mathrm{get(x)}\) 函数返回 \(x\) 所处的块的编号。可以这样写
int get(x) { return (int)x / S; } - 查询端点。\(\mathrm{getl/getr}\)，返回当前块的左、右端点。可以这样写（前提是你的
get函数和我一样。）
int getl(int x) { return S * x + (x == 0); }
int getr(int x) { return min(n, (x + 1) * S - 1); }
拿 数列分块入门1 举个栗子。
题意： 给定长度为 \(\mathrm{n}\) 的数列，进行 \(\mathrm{n}\) 次操作。操作涉及区间加法，单点查询。
这种题当然可以 线段树 / 树状数组，但是今天我们要用分块来写。按照上面我们说的。借鉴线段树的思路，我们可以维护一个 \(\mathrm{add}\) 懒标记，来维护当前块应该加上几。
现在假设我们修改的区间是 \(\mathrm{[l, r]}\)，可能有下面几种情况。
- 左右端点在同一个块里。我们遍历 \(\mathrm{l \sim r}\)，暴力加即可。复杂度 \(\mathrm{O(\sqrt{n})}\)
- 左右端点不在同一个块里。我们可以遍历中间的整块并打上懒标记。由于块数不超过 \(\mathrm{O(\sqrt{n})}\) 个，所以复杂度也不高。对于不在整块内的边角，直接暴力加就可以。
核心代码
int get(int x) { return x / S; } // 定位当前点在哪个块
void modify(int l, int r, int v) { // 修改操作
int ls = get(l), rs = get(r);
if (ls == rs) { for (int i = l; i <= r; i ++ ) w[i] += v; return; } // 在同一个整块内
int i, j;
for (i = l; get(i) == ls; i ++ ) w[i] += v; // 处理边角
for (j = r; get(j) == rs; j -- ) w[j] += v;
for (int k = get(i); k <= get(j); k ++ ) // 处理整块。
add[k] += v;
}
int main() {
.......
if (query node) printf("%d\n", w[r] + add[get(r)]);
else modify(l, r, v);
}
其他例题
数列分块入门7
题意： 给出一个长为 \(n\) 的数列，以及 \(n\) 个操作，操作涉及区间乘法，区间加法，单点询问。
可以对照线段树2来做。对每个块维护加、乘懒标记。注意：懒标记更新的时候注意顺序，对散块操作的时候要重构整个块。
代码示例
数列分块入门2
题意： 给出一个长为 \(n\) 的数列，以及 \(n\) 个操作，操作涉及区间加法，询问区间内小于某个值 \(x\) 的元素个数。
分块常用的思想，就是在每个块内维护一个有序序列。加操作时可以打懒标记。查询操作可以直接块内二分。单次操作复杂度 \(\mathrm{O(\sqrt{n} \log n)}\) （ \(\log \sqrt{n}\) 和 \(\log n\) 同阶）
代码示例
数列分块入门5
这道题带插入怎么办呢？块状链表隆重登场！！
块状链表可以看一下我写的博客 块状链表详解
剩下的就不讲了吧，再放几道例题。
例题
-
数列分块全系列
-
某些线段树题（比如洛谷线段树模板）
-
其他题目，如 Luogu 分数统计
以后可能还会加例题。先挖个坑。
标签：入门,分块,int,复杂度,sqrt,详解,操作,mathrm From： https://www.cnblogs.com/LcyRegister/p/17060561.html