主题 作者
- 09
- 14
- 3
- 文章类型
- 完全原创 —— 转载请标注作者
【数据结构】根号系列 1 —— 分块
前言
分块是一种简单的算法，可以说，它是最接近暴力的算法，或许与你的常识相违，它在复杂的场景下恰恰会是最有用的。
分块是多种多样的，读者会遇到的，最难的分块算法题，无疑是树分块（tree cluster），或者大分块（多种数据结构）。
由于这部分难度较大，涉及诸多前置知识，包括一些论文内容，因此本文并不涉及这些内容。
本文主要介绍四部分内容，请按顺序阅读
- 序列分块
- 值域分块
- 前缀和、差分
- 四个有趣的分块技巧
值得注意的是，本文不会涉及复杂数据结构。
本文为我原创，如需转载，请注明作者为玉藻前。
序列分块
序列分块主要用于维护区间信息，它将一个长度为 [imath]n[/imath] 的区间，分成 [imath]\sqrt n[/imath] 个长度为 [imath]\sqrt n[/imath] 的，互不相交的块。
假设说有一种操作，需要将修改应用到 [imath]O(n)[/imath] 个元素上，那么 每次 暴力修改，需要的时间至少是 [imath]O(n)[/imath] 的。
不妨举个例子：
给你一个长度为 [imath]n[/imath] 的数组 [imath]a[/imath]，一共有 [imath]q[/imath] 个操作
- 区间求和：输出 [imath]a_l+ a_{l+1}+\dots + a_r[/imath]
- 区间加法：使 [imath]a_l, a_{l+1}, \dots , a_r[/imath] 全部加上 [imath]x[/imath]
实际上，写一个 for 就可以简单求解，但是很不幸的是，算法整体的复杂度是 [imath]O(qn)[/imath] 的，我们希望优化这个做法。
分块的想法和其他区间数据结构一样，通过将一些共有的信息进行合并，避免每次暴力更新 所有 需要修改的元素。
由于这个问题对于新手而言还是太难了，不妨让我们考虑其简化版，即去掉操作 2。
给你一个长度为 [imath]n[/imath] 的数组 [imath]a[/imath]，一共有 [imath]q[/imath] 个操作
- 区间求和：输出 [imath]a_l+ a_{l+1}+\dots + a_r[/imath]
如果我们暴力写一个 for 来求解，复杂度当然是 [imath]O(qn)[/imath] 的，让我们看看分块是怎么做的？
分块将这个长度为 [imath]n[/imath] 的区间，分成 [imath]\sqrt n[/imath] 个长度为 [imath]\sqrt n[/imath] 的，互不相交的块（最后一个块大小可以小于根号）。
为 每个 块设立一个变量 [imath]sum[/imath]，其意义为，这个块内的元素之和。
假设说，方块是原始序列，分块的块长为 [imath]3[/imath]， 且黑色部分是本次询问的部分，需要输出它们的和
□□□ □■■ ■■■ ■■■ ■■■ ■□□ □□
不难发现，有一些 块 是被完全覆盖了的，我们称之为『整块』，此外
在最左，最右，最多 还会有 两个 块，被部分覆盖了，我们称之为『散块』
□□□ □■■ ■■■ ■■■ ■■■ ■□□ □□
由于我们已经预处理出了，每个块内，所有元素的和 [imath]sum[/imath]，对于『整块』，我们可以 [imath]O(1)[/imath] 地求和
而最多有 [imath]\sqrt n[/imath] 个块，所以这部分的整体复杂度为 [imath]O(\sqrt n)[/imath]
我们前面说过，分块是一个暴力算法，所以对于『散块』，我们直接暴力求解，用 for 做加法：
每次询问，最多有 [imath]2[/imath] 个散块，每个散块的大小都不大于 [imath]\sqrt n[/imath]（这是前面，你自己定的大小）
因此这部分的复杂度也是 [imath]O(\sqrt n)[/imath]
至此，我们可以在 [imath]O(\sqrt n)[/imath] 的时间里回答每个询问，
那么，算法的整体复杂度为 [imath]O(q\sqrt n)[/imath]
尽管肉眼可见地，『 [imath]O(qn)[/imath]的暴力算法』 和『 [imath]O(q\sqrt n)[/imath]的分块算法』 的时间复杂度差了一个根号，
你可能依然好奇，它们在实际运行中，到底会有多少性能差距？
不妨以 [imath]n = q = 10^5[/imath] 举例，此时 [imath]\sqrt n \ = 316[/imath]
虽然这么说并不准确，但是在排除常数影响后，分块的性能是暴力算法的 [imath]316[/imath] 倍，且随着数据量级的增长，差距会越来越大！
让我们回到最初的问题，依然去掉一个操作，不过是另一个：
给你一个长度为 [imath]n[/imath] 的数组 [imath]a[/imath]，一共有 [imath]q[/imath] 个操作
- 区间加法：使 [imath]a_l, a_{l+1}, \dots , a_r[/imath] 全部加上 [imath]x[/imath]
事实上，『加法』是一个可以合并的操作，它满足结合率，交换律：
- 结合率：1 + 2 + 3 + 4 = 10，我们可以把 [imath]O(n)[/imath] 个信息合并成仅 [imath]1[/imath] 个。
- 交换律：1 + 2 + 3 = 3 + 2 + 1，操作的顺序是无所谓的。
在得到这两个强力性质后，我们可以考虑这个问题 —— 怎么合并这些修改信息？
□□□ □■■ ■■■ ■■■ ■■■ ■□□ □□
对于『整块』，我们很自然地可以想到，为每个块单独设置一个变量，比如叫 [imath]tag[/imath]
[imath]tag[/imath] 的值用于代表：块内每个元素，都被加上了 [imath]tag[/imath] 的值，这样就维护好了每个块的信息！
每次修改，我们对于『整块』，有 [imath]tag_i = tag_i + x[/imath]
对于『散块』，我们直接暴力修改区间内每个元素，[imath]a_i = a_i + x[/imath]
整体的时间复杂度依然是 [imath]O(q\sqrt n)[/imath] 的，详细的证明可以留给读者，分析过程与前面的一样。
给你一个长度为 [imath]n[/imath] 的数组 [imath]a[/imath]，一共有 [imath]q[/imath] 个操作
- 区间求和：输出 [imath]a_l+ a_{l+1}+\dots + a_r[/imath]
- 区间加法：使 [imath]a_l, a_{l+1}, \dots , a_r[/imath] 全部加上 [imath]x[/imath]
聪明的读者一下子就明白了，我们只要把上面的结合起来就行了！
□□□ □■■ ■■■ ■■■ ■■■ ■□□ □□
询问操作（区间求和）：
设置一个答案变量 [imath]res[/imath]，
对于每个『整块』，[imath]res = res + sum_i[/imath]
对于每个『散块』，[imath]res = res + a_i[/imath]
修改操作（区间加法）：
单纯的区间加法是很简单的，我们前面已经提过了
但是现在有一个问题，区间加法的 [imath]tag[/imath] 和 区间求和的[imath]sum[/imath] 是相互独立的
事实上，假设某个块（假设有 [imath]k[/imath] 个元素），被整体加上了 [imath]x[/imath]
那么应该要作出修改，使 [imath]sum = sum + kx[/imath]
对于被覆盖的『整块』，由于我们知道每个块内有多少个元素（假设有 [imath]k[/imath] 个）
所以每次我们在修改完 [imath]tag_i[/imath] 后，可以使 [imath]sum_i = sum_i + kx[/imath]
对于『散块』内被覆盖的元素，我们每次暴力修改后，同时修改 [imath]sum[/imath]
即 [imath]a_i = a_i + x[/imath] 的同时，[imath]sum_i = sum_i + x[/imath]
不难证明，整体的时间复杂度依然是 [imath]O(q\sqrt n)[/imath] 的
分块的分治程度低于各类区间数据结构（如线段树），前者名为根号分治，后者则名为中点分治。
线段树每次在区间中点进行一次分块操作，不难发现，一个长度为 [imath]n[/imath] 的区间，在不超过 [imath]O(log)[/imath] 次折半后，降低为 [imath]1[/imath]
于是线段树的高度为 [imath]O(\log n)[/imath]，实际上，是一颗二叉树。
同样地，分块，要求每个块的最大大小在 [imath]O(\sqrt n)[/imath] 级别
由于其特殊性质，也可以被视作是一颗高度为 [imath]2[/imath] 或 [imath]3[/imath] 的，非常扁平的树。
值域分块
值域分块本质是序列分块的特殊应用，相当于一种模型转化，用于解决以下问题：
问题一：
给你一个序列 [imath]a[/imath]，初始有 [imath]10^5[/imath] 个数，支持以下操作：
- 增 / 删一个数 [imath]x[/imath]
- 求整个序列中，满足 [imath]l \le a_i \le r[/imath] 的数有多少个
保证初始的元素，以及增删的数，都 [imath]\in [0, 10^5][/imath]
我们引入一个概念 —— 桶 [imath]b[/imath]
[imath]b_i[/imath] 的含义如下：[imath]i[/imath] 代表数字 [imath]i[/imath]，[imath]b_i[/imath] 的值代表数字 [imath]i[/imath] 出现了多少次
比如说：
原始序列 为 1 2 3 5 5 5
桶的序列 为 1 1 1 0 3 0
在转换为桶后，我们不难发现，上述值域分块问题，就可以用和序列分块完全一样的代码解决了
时间复杂度： [imath]O(q\sqrt n)[/imath]
问题二：
给你一个序列 [imath]a[/imath]，初始有 [imath]10^5[/imath] 个数，支持以下操作：
- 增 / 删一个数 [imath]x[/imath]
- 求整个序列中，满足 [imath]l \le a_i \le r[/imath] 的数有多少个
- 求第 [imath]k[/imath] 小
- 求 [imath]mex[/imath]
第 [imath]k[/imath] 小的定义是，数组从小到大排序后，第 [imath]k[/imath] 个数字
[imath]mex[/imath] 指的是从 0 开始算，第一个没有出现过的整数
保证初始的元素，以及增删的数，都 [imath]\in [0, 10^5][/imath]
求第 k 小很方便，我们开一个计数器，从 0 开始，直接整块地跳，
假如加入了某个块的 [imath]sum[/imath] 以后，这个计数器的值大于等于 k 了，
那么答案就在这个块内，在块内暴力往前计数即可，单次查询复杂度为 [imath]O(sqrt n)[/imath]
求 [imath]mex[/imath] 则需要你对桶进行一下改造，如果某个数存在，他的桶的值为 1，不论存在多少个。
不存在则为 0。
由于我们知道每个块的长度，如果这个块的 [imath]sum[/imath] 小于块的长度，
答案一定就在这个块内，块内暴力往前即可，依然 [imath]O(\sqrt n)[/imath]
我们可以在 [imath]O(q\sqrt n)[/imath] 时间内解决这个问题
问题三：
假设读者不会离散化，可以无视这个问题。
给你一个序列 [imath]a[/imath]，初始有 [imath]10^5[/imath] 个数，支持以下操作：
- 增 / 删一个数 [imath]x[/imath]
- 求整个序列中，满足 [imath]l \le a_i \le r[/imath] 的数有多少个
- 求第 [imath]k[/imath] 小
- 求 [imath]mex[/imath]
保证初始的元素，以及增删的数，都 [imath]\bold{ \in [0, 10^9]}[/imath]
这时候我们会发现，桶的空间过于大了，我们无法开那么大的内存空间。
这个时候，对于前三个操作，只需要离散化一下，就可以解决这个问题。
第四个操作则需要一个前提，操作的次数是有限的，例如 [imath]10^5[/imath] 次。
作为 [imath]mex[/imath] 的数字，前面的桶必然全部是 [imath]1[/imath]。假设一共有 [imath]k[/imath] 个数字，那么答案一定不会超过 [imath]k[/imath]
于是你不离散化，直接丢掉大于 [imath]k[/imath] 的数字
不难发现，这一切都是序列分块，而你在分块基础上，对储存、合并的信息进行调整，以此来解决不同的问题。
前缀和
前缀和与差分是一组可以相互抵消的运算。
定义 前缀和 数组 [imath]pre[/imath]：
[imath]pre_1 = a_1[/imath]
[imath]pre_x = a_1+ a_2 \dots + a_x[/imath]
不难发现，定义式可以写成递推式的形式
[imath]pre_i = pre_{i-1} + a_i[/imath]
我们可以在 [imath]O(n)[/imath] 的时间内求出长度为 [imath]n[/imath] 的原序列的前缀和数组 [imath]pre[/imath]
考虑怎么解决 不带修改 的区间求和：
[imath]\displaystyle\sum_{i=L}^R a_i = pre_R - pre_{L-1}[/imath]
可以在 [imath]O(1)[/imath] 的时间内求解。
考虑怎么解决 单点修改 的区间求和：
假设 [imath]a_x = a_x + 1[/imath]，那么会导致以下修改： [imath]pre_x，pre_{x+1}，\dots ，pre_{n}[/imath] 全部加上 [imath]1[/imath]
那么修改的复杂度为 [imath]O(n)[/imath]，求和的复杂度为 [imath]O(1)[/imath]
修改的成本有点太高了，在后文，我们可以研究如何使用分块，将前者的复杂度降低至 [imath]O(\sqrt n)[/imath]
差分
前缀和与差分是一组可以相互抵消的运算。
定义 差分 数组 [imath]suf[/imath]：
[imath]suf_1 = a_1[/imath]
[imath]suf_i = a_i - a_{i-1}[/imath]
我们可以在 [imath]O(n)[/imath] 的时间内求出长度为 [imath]n[/imath] 的原序列的差分数组 [imath]suf[/imath]
考虑怎么解决 区间加法：
[imath]suf_{L} = suf_{L} + x[/imath]，[imath]suf_{R+1} = suf_{R+1} - x[/imath]
可以在 [imath]O(1)[/imath] 的时间内完成。
考虑怎么解决 区间求和：
将差分数组做一次前缀和，即可还原，得到原数组，此后暴力地求和，复杂度 [imath]O(n)[/imath]
求和的成本有点太高了，在后文，我们可以研究如何使用分块，将复杂度降低至 [imath]O(\sqrt n)[/imath]
四个有趣的分块技巧
前缀分块：
每个块内元素 [imath]a[/imath] 做前缀和，每个块的 [imath]sum[/imath] 间做前缀和
那么可以实现 [imath]O(1)[/imath] 区间求和，[imath]O(\sqrt n)[/imath] 区间加法
应用场景：
莫队二次离线，等（有 [imath]n[/imath] 次修改，有 [imath]n\sqrt n[/imath] 次询问 -> 这是一种不平衡的场景，操作的数量级不一样）
而我们发现，前缀分块本身也是不平衡的算法，修改和查询的复杂度不一样
我们用不平衡来对抗不平衡！
也许有同学学习过平衡树，或者是二叉树、堆，一类的东西，知道我们可以 [imath]O(log)[/imath] 的时间内修改 + 查询
看起来他们更优秀，但是我们可以仔细思考，在不平衡的场景下，会发生什么？
前缀分块：
- 单次修改：[imath]O（\sqrt n）[/imath]
- 单次查询：[imath]O（1）[/imath]
- 总复杂度（有 [imath]n[/imath] 次修改，有 [imath]n\sqrt n[/imath] 次询问）
- 修改：[imath]O（n\sqrt n）[/imath]
- 查询：[imath]O（n\sqrt n）[/imath]
平衡树等高级数据结构：
- 单次修改：[imath]O（\log n）[/imath]
- 单次查询：[imath]O（\log n）[/imath]
- 总复杂度（有 [imath]n[/imath] 次修改，有 [imath]n\sqrt n[/imath] 次询问）
- 修改：[imath]O（n\log n）[/imath]（复杂度降低了）
- 查询：[imath]O（n\sqrt n \log n）[/imath] （复杂度太高了，在 [imath]10^5[/imath] 量级下，比分块慢了 20 倍）
差分分块：
每个块内元素 [imath]a[/imath] 做差分，每个块的 [imath]sum[/imath] 间做差分
那么可以实现 [imath]O(1)[/imath] 区间加法，[imath]O(\sqrt n)[/imath] 区间求和
应用场景：
大分块题等。但是由于这个差分分块本身很简单好想，所以在这里提及。
数组分块 / 分块链表：
我们知道，在一个地址连续的，长度为 [imath]n[/imath] 的数组中间（而非两边）插入一个元素，其复杂度是 [imath]O(n)[/imath] 的
假设我们把一个长度为 [imath]n[/imath] 的数组，分割成 [imath]\sqrt n[/imath] 个数组，每个数组长度为 [imath]O(\sqrt n)[/imath]
那么在任何一个地方插入数字，其复杂度是 [imath]O(\sqrt n)[/imath] 的
基于这种想法，我们可以实现:
[imath]O(\sqrt n)[/imath] 插入/删除一个数，[imath]O(1)[/imath] 查询整个数组中第 [imath]k[/imath] 小的元素，等
可能有人会问，前面值域分块的复杂度不也是一样的吗？
错错错，这种做法可以无视值域，也不需要离散化！
指数分块：
也许有人知道快速幂，它允许你在 [imath]O(log \omega)[/imath] 时间内计算 [imath]x^{\omega}[/imath] 的值（[imath]\omega[/imath] 为正整数）
但是假设 [imath]x[/imath] 是固定的，且有 [imath]n\sqrt n[/imath] 次询问，上述做法就会很慢，变成 [imath]O（n\sqrt n \log{\omega}）[/imath]
这里介绍一种对指数分块的做法，假设 [imath]\omega[/imath] 是指数的上限：
预处理：
- 求出 [imath]x^1, x^2, x^3, \dots,x^{\sqrt \omega}[/imath] -> [imath]O(\sqrt n) - time[/imath]
- 求出 [imath]x^{\sqrt \omega},x^{2 \sqrt \omega}, x^{3 \sqrt \omega}, \dots, x^{\omega}[/imath] -> [imath]O(\sqrt n) - time[/imath]
不难发现，我们总是可以把 [imath]x^{k}[/imath] 分解为 [imath]x^{a} * x^{b \sqrt{\omega}}[/imath]，这两者都已经被分别预处理出来了
于是我们通过花费 [imath]O(\sqrt n) - time[/imath] 来预处理，得到了一个 [imath]O(1)[/imath] 回答的优秀算法。
结语
分块看起来是一种定式，是一种暴力的算法，但实际上，它是一种根号分治的思维。
假设某些元素共有的信息可以合并，我们便尽可能地，将一个块内共有的信息提取出来，单独存放，单独修改。
本文举的例子非常浅显易懂，但是实际上，有相当多的信息无法直接叠加，操作的时序也无法被调换，
这种时候，我们就要分析信息的特殊性质，改造你的分块，让它维护别的信息（比如上文，我们维护的是块内的和 [imath]sum[/imath]）
这是分块本身的魅力所在，它极其接近信息本身，你便要动脑去思考怎么解决问题。
我相信在思考（解题）的过程中，你可以对信息学本身，有更深的兴趣和理解。
基于分块，我们有很多高级算法，莫队，莫队二次离线，大分块（分块+高级数据结构），树分块，等，
基于一些科技（神奇的论文算法），分块得到了更大的强化
例如：可以用线段树维护分块（叶子节点是块），又或者加速二分过程，去掉一个 [imath]log[/imath]，实现了 [imath]O(n)[/imath] 在 [imath]n[/imath] 个块内二分
更令人害怕的是，上述做法的空间复杂度都是 [imath]O(n)[/imath] 的
我们都会在后面的文章内介绍他们。
感谢您的阅读，如有不理解之处，请在下方回复！
如本文出现疏漏、错误，请及时联系，非常感谢读者的支持。
由版主最后编辑：