分块全家桶

煮波在怒艹 SATT 所以咕着

好了艹不过去我回来写了。

0. 序列分块#

我们看这样一道题：

区间加，单点求值

您一眼秒了它，这不是 BIT 板子吗？好，但是我让你用暴力过这道题，怎么办呢？

我们可以把这个序列分成若干块，设块的长度为 $B$。对于每个更新的区间，我们一定能把它拆成一些整块，没拆完的我们把它称作散块。

每次更新，我们可以对整块用懒标记的方式整体更新，然后对于散块，我们直接暴力修改。整块更新的复杂度是 $\Omicron(\frac{n}{B})$，因为散块长度不可能大于 $B$，所以散块更新的复杂度是 $\Omicron(B)$ 的，总复杂度是 $\Omicron(B + \frac{n}{B})$。

现在我们来确定块长，我们要让这个式子取最小值，聪明的你一定看出来这是个双勾函数，取 $\sqrt{n}$ 最优。

这个值一般是会变的，视题目而变。

你可能会问，既然有更优的 $\log$ 数据结构，那我为什么要用分块？

因为分块的实质就是优化暴力，线段树之类的数据结构要求信息构成一个半群，一旦信息没有结合律就不能维护，而分块就没有这个限制，你只要能考虑好整块如何在比较低的复杂度内处理就行。

分块入门 LOJ 有 $9$ 道，我觉得挺适合入门的。

1. 莫队#

这个其实就是利用了分块思想与双指针，核心是在排序上。

我们发现，如果问题支持我们在低复杂度下将 $[l,r]$ 的答案扩展到 $[l,r + 1],[l,r - 1],[l + 1,r],[l - 1,r]$，那我们就可以用类似双指针的方法来求出所有问题的答案，每次通过指针移动来计算出应该怎么让答案变化。

很明显，这个可以给你卡到单次 $\Omicron(n)$，聪明的你一定想到排下序，对相同的左端点就可以一趟过去就求完了，但是这样还是能卡你，有没有什么办法呢？有的兄弟，有的，我们可以用分块思想。

我们确定一个块长 $B$，然后，我们按照左端点所在的块为第一关键字，右端点为第二关键字排序，然后像上面一样处理。这样，一个块内的询问，左端点最多只会移动 $\Omicron(B)$ 次，右端点会移动 $\Omicron(n)$ 次，总复杂度是 $\Omicron(B(n + m))$ 的，取 $B = \sqrt{n}$ 最优。

观察到这个太暴力了，肯定需要优化，有个常见的是奇偶化排序，就是奇数块的右端点按升序，偶数块的按降序排序，这样回来的时候会顺便处理偶数块的询问。

其他莫队本人还在学 /

2. 值域分块#

和其他维护值域的 DS 一样，对桶数组分块就成了值域分块，一样可以拿来解决求排名求 K 小值的问题。

分完块后，单点修改是 $\Omicron(1)$ 的，对区间查询是 $\Omicron(\sqrt{n})$ 的，很普通的分块。

但是，我们还可以换一种思路：对所有整块维护前缀和，块内也维护前缀和，那这样区间查询就可以做到 $\Omicron(1)$ 了，修改变为 $\Omicron(\sqrt{n})$，对于查询复杂度太高的分块可以这么搞。

那你可能要问了：不刷 Ynoi 的话那我为什么不选 $\log$ 的 DS 呢？

我们看下面这道题：

多次询问，每次求区间 $[l,r]$ 中值属于 $[a,b]$ 的数值个数。

一眼我们可以发现，这就是个区间数区间颜色。外面可以直接莫队，那里面这个该用什么呢？我们当然可以树状数组，但是，我们也可以用值域分块，用 $\Omicron(1)$ 修改，$\Omicron(\sqrt{n})$ 查询的那个，这样就能做到 $\Omicron((n + m) \sqrt{n})$，比树状数组整整少了一个 $\log$ ！。

当然我还是会直接写 BIT

3. 块状链表#

这个东西可以做到 $\Omicron(\sqrt{n})$ 支持插入，删除，查询，分裂，合并，相当于根号算法里面的的链表/平衡树。

实现就是一个链表，链表每个节点代表原序列的一个块，块的大小不超过 $2B$，一般存储一个数组。如果超过 $2B$ 就分裂，分裂为两个大小为 $B$ 的块，以此来保证复杂度。

插入就像链表一样，直接遍历来找到对应的位置，然后插入到内层数组中，删除也一样。明显的，你可以在块里面再维护些东西来支持带插区间操作。

可以支持某些平衡树的区间操作，只要能支持散块暴力，整块打标记就可以。好像可以可持久化，但是我觉得意义不明，而且带插的可持久化好像也没啥用。