分块算法，和莫队有着异曲同工之妙，是一种优雅的暴力。
概述
分块算法，顾名思义是把一个长度为 $n$ 的序列分成 $m$ 块，每块的大小均为 $\frac{n}{m}$。我们维护块内信息，使得块内信息的查询是 $O(1)$ 的，而总的询问又可以看做是若干个块的询问的总和。
为了方便描述，我们定义：
- 完整块：区间操作时，完整包含于区间的块。
- 不完整的块：区间操作时，只有部分包含于区间的块，即左右端点所在的两个块。
- 零散元素：不完整的块内的元素。
我们发现，对于一个询问 $[l,r]$，我们可以进行如下处理：
- 拆成若干个完整块，其中每个完整快内的信息可以 $O(1)$ 更新。其中完整块的数量为 $O(\frac{n}{m})$。
- 剩下两个不完整的块，对于这两个块内的信息暴力更新。其中不完整的块的大小为 $O(m)$。
综上所述，分块算法单次操作的时间复杂度为 $O(\frac{n}{m}+m)$。根据均值不等式，我们可以发现 $m=\sqrt n$ 时复杂度最优。
如何分块
我们定义如下变量：
| $len$ | $num$ | $bl[i]$ | $l[i]$ | $r[i]$ |
|---|---|---|---|---|
| 块的大小 | 块的数量 | 第 $i$ 个元素所属的块 | 第 $i$ 个块的左端点 | 第 $i$ 个块的右端点 |
那么我们可以用如下代码建立分块：
其中特别需要注意
r[num]=n意味着第 $num$ 个块（最后一个块）的右端点一定是 $n$！
1 |
void build() { |
接下来我们就用 $9$ 个来自 LOJ 的例题（可能稍有修改）来简单讲解一下分块的思想。
例题 1
给定一个长度为 $n$ 的序列和 $m$ 个操作。支持区间加法，单点求值。
Solution
我们用 $tag[i]$ 记录第 $i$ 个块内每个元素都加的值。
对于修改操作 $[x,y]$ 有两种情况：
- 其中 $x$ 和 $y$ 在同一个块内，那么直接暴力修改 $a[i]$ 的值即可。
- 其中 $x$ 和 $y$ 不在同一个块内，那么先修改整块 $(bl[x],bl[y])$ 的 $tag$ 值，然后再对 $x$ 和 $y$ 所在的块内的零散元素暴力修改 $a[i]$ 的值。
对于查询操作 $x$，直接输出 $a[x]+tag[bl[x]]$ 的值。
时间复杂度：$O(m\sqrt n)$
Code
1 |
|
例题 2
给定一个长度为 $n$ 的序列和 $m$ 个操作。支持区间加法，区间查询小于 $v$ 的元素个数。
Solution
我们首先考虑没有修改操作怎么做：
- 对于零散元素，我们直接暴力查找。
- 对于整块，我们可以先排序然后直接二分查找。
如果有了修改操作，那么意味着我们每次修改后需要重新排序，还是分成两部分考察：
- 对于零散元素，我们暴力修改后对不完整块直接重新排序。时间复杂度为 $O(\sqrt n\log n)$。
- 对于整块，我们发现修改不影响元素之间的相对顺序，所以不需要排序。查询时需要用 $v-tag[i]$ 的值二分查找。时间复杂度为 $O(\sqrt n)$。
时间复杂度：$O(m\sqrt n\log n)$（其中可以用均值不等式计算出更优的复杂度 QAQ）
Code
1 |
|
例题 3
给定一个长度为 $n$ 的序列和 $m$ 个操作。支持区间加法，区间查询 $v$ 的前驱。
Solution
我们有一个很直观的想法：直接沿用例题 2 的思路，只要修改一下二分即可。
但是这题有一个更简单的方法，直接用 $\text{set}$ 维护块内信息。这样甚至可以支持插入和删除操作，更加方便。但是 $\text{set}$ 常数巨大，所以此题不建议使用 $\text{set}$ 来维护。
时间复杂度：$O(m\sqrt n\log n)$
Code
直接二分查找
1 |
|
使用 $\text{set}$ 维护
1 |
|
例题 4
给定一个长度为 $n$ 的序列和 $m$ 个操作。支持区间加法，区间求和。答案对 $10^9+7$ 取模。
Solution
这题还是和例题 1 一样的思路，只不过需要多维护一个区间和：我们定义 $sum[i]$ 表示第 $i$ 个块的总和（不包括 $tag[i]$ 的值，也就是说这两者是独立的）。
我们先分析修改操作，对于两种情况分类讨论：
- 对于零散元素，我们暴力修改 $a[i]$ 和 $sum[bl[i]]$ 的值。
- 对于整块，只需要修改 $tag[i]$ 的值即可，而不需要修改 $sum[i]$ 的值。
我们再分析查询操作，对于两种情况分类讨论：
-
对于零散元素，我们用 $a[i]+tag[bl[i]]$ 来更新答案。
-
对于整块，经过简单的思考就可以发现答案就是 $sum[i]+tag[i]\times len$ 的总和。
为什么可以直接用 $len$ 的值？因为我们在统计时，只使用 $(bl[x],bl[y])$ 这个闭区间内的整块，不涉及最后一个块，所以每个块的大小必为 $len$。
时间复杂度：$O(m\sqrt n)$
Code
1 |
|
例题 5
给定一个长度为 $n$ 的序列和 $m$ 个操作。支持区间开方，区间求和。
Solution
由于有区间开方操作，没法直接更新区间和，问题貌似比较棘手。
但是我们可以分析一下开方的性质：一个 $10^9$ 的数字不断进行开方，其值大约为：$10^9,31622,177,13,3,1,1,1,\cdots$
那么意味着，每个数最多被开方大约 $5$ 次，这样我们可以记录每个块中是否有 $>1$ 的元素。如果没有则不需要对这个块内元素开方操作。
有了这个性质，直接暴力操作即可。
时间复杂度：$O(m\sqrt n)$
Code
1 |
|
例题 6
给定一个长度为 $n$ 的序列和 $m$ 个操作。支持单点插入，单点求值。
Solution
首先考虑数据随机的情况，那么每个块内插入的操作是均摊的。我们只需要用 $\text{vector}$ 维护每个块，暴力插入查询即可，时间复杂度依旧为 $O(m\sqrt n)$。
我们发现，在极限数据下，某个块内可能会被插入至多 $O(m)$ 次，这样单次操作的复杂度就变成了 $O(m)$，显然是不能接受的。
我们发现，当一个块的大小过大时就会影响整体的复杂度。那么我们在块过大时进行重构分块，我们定义一个阈值 $k$，当某个块的大小超过 $k\times len$ 时，我们对整个序列进行重构。一般而言，这个阈值 $k$ 在 $20$ 左右复杂度较优。
当然还有一个方法：每进行 $\sqrt n$ 次插入操作后就进行重构。每次重构的复杂度为 $O(n+m)$，那么总体的复杂度还是 $O(m\sqrt n)$（默认 $n$ 和 $m$ 同阶）。
时间复杂度：$O(m\sqrt n)$
Code
1 |
|
例题 7
给定一个长度为 $n$ 的序列和 $m$ 个操作。支持区间乘法，区间加法，单点求值。答案对 $10007$ 取模。
Solution
我们发现修改操作和「Luogu 3373」【模板】线段树 2 的套路非常相似。
首先我们强制乘法比加法优先。也就是说，块内维护两个标记 $add[i]$ 和 $mul[i]$ 分别表示整个块内加、乘的值。一个元素 $a[i]$ 实际表示的值为 $a[i]\times mul[bl[i]]+add[bl[i]]$。
- 块内乘法 $v$：假如两个标记的值为 $A$ 和 $M$，那么标记变成 $A\times v$ 和 $M\times v$。
- 块内加法 $v$：假如两个标记的值为 $A$ 和 $M$，那么标记变成 $A+v$ 和 $M$。
对于零散元素，我们无法直接修改，所以直接暴力将所在块内的标记转移到元素上，然后将标记清空（$add[i]=0,mul[i]=1$），直接对零散元素本身修改即可。
Code
1 |
|
例题 8
给定一个长度为 $n$ 的序列和 $m$ 个操作。支持区间查询等于 $v$ 的元素个数并覆盖为 $v$。
Solution
我们先考虑一个暴力的做法，对于修改操作：
- 对于零散元素，我们暴力修改。注意单点修改前需要下放标记！
- 对于整块，我们对这个块打上标记，表示整个块内的元素相同，均为 $v$。
然后考虑查询操作：
- 对于零散元素，我们下放标记后暴力查询。
- 对于整块，如果这个块内有标记且标记的值为 $v$，那么对答案有 $len$ 的贡献。如果没有标记，那么我们对 $[l[i],r[i]]$ 区间内的元素暴力查询。
这个做法看上去单次查询的复杂度为 $O(n)$，但是我们这样分析：
假设初始序列都是同一个值，那么单次查询的复杂度为 $O(\sqrt n)$。如果这是进行一个区间操作，它最多破环首位 $2$ 个块的标记，所以只能使得后面的询问至多增加 $2$ 个块的暴力时间，所以均摊的单次复杂度为 $O(\sqrt n)$。
换句话说，要让一次操作耗费 $O(n)$ 的时间，要先花费 $O(\sqrt n)$ 个操作对数列进行修改！综上所述，总体时间复杂度为 $O(m\sqrt n)$。
时间复杂度：$O(m\sqrt n)$
Code
1 |
|
例题 9
给定一个长度为 $n$ 的序列和 $m$ 个操作。支持区间查询最小众数。
Solution
以下解法中，我们为了方便表述，定义 $\text{mode}(i)$ 表示第 $i$ 个整块的众数。
解法 1（无修改）
我们首先可以发现一个性质：对于询问 $[x,y]$，答案 $\in\text{mode}(i\sim j)\cup\text{零散元素}$（其中 $\text{mode}(i\sim j$) 表示 $[x,y]$ 内的所有整块的众数）。令 $l,r$ 分别在第 $a,b$ 块，那么 $[l,r]$ 可以拆成：
- 从 $l$ 到第 $a$ 块的最后一个元素。
- 从第 $a+1$ 块到第 $b-1$ 块。
- 从第 $b$ 块的起始一个元素到 $r$。
根据这个性质，我们只需要至多比较 $2\sqrt n+1$ 即 $O(\sqrt n)$ 个数的出现次数即可。
那么我们可以 $O(n\sqrt n)$ 预处理 $f[i][j]$ 表示第 $i$ 个整块到第 $j$ 个整块的众数。然后对于每个种值开一个 $\text{vector}$ 记录值 $i$ 出现的位置。
接下来考虑询问 $[x,y]$ 怎么分解处理：
- 对于零散元素，我们暴力查找每个元素在 $[x,y]$ 内的出现次数，这个过程可以通过在记录 $a[i]$ 出现位置的 $ve[a[i]]$ 内二分查找实现。
- 对于整块，众数为 $f[bl[x]+1][bl[y]-1]$，出现次数同理可以二分得到。
我们只需要在这 $O(\sqrt n)$ 个数内找到出现次数最多的数即可。
注意，为了方便计算需要事先对数据离散化。
时间复杂度：$O(m\sqrt n\log n)$（可以通过均值不等式计算出块的大小为 $\sqrt{\frac{n}{\log n}}$ 以获得更优的复杂度通过本题）
期望得分：$80\sim100$
解法 2（无修改）
我们考虑在解法 1 的基础上进行修改。首先 $\sqrt n$ 这个系数是肯定没法去掉了，考虑如何仍然在 $\sqrt n$ 分块下去掉 $\log n$ 这个系数。这意味着我们要在 $O(1)$ 的时间内回答询问。
不妨设 $F[i][x]$ 表示 $[0,i]$ 之间有多少个 $x$。那么 $[l,r]$ 之间的 $x$ 的数量就是 $F[r][x]-F[l-1][x]$，所以可以省去一个二分的 $\log n$。
预处理时，我们只需要对序列扫一遍即可，复杂度为 $O(n)$。
时间复杂度：$O(m\sqrt n)$
期望得分：$100$
解法 3（带修改）
貌似可以 $\sqrt[3] n$ 分块？推荐阅读 区间众数解题报告 - 陈立杰 改日填坑
Code
解法 1
1 |
|
解法 2
1 |
// 改日填坑 |
解法 3
1 |
// 改日填坑 |
习题
- Ynoi 吼啊！
改日填坑