最近写了几个分块,顺便做一下笔记。
什么是分块
分块是一种数据结构。。
有许多数据结构都是 \(\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