##分块思想
利用分块的思想设计出的算法其复杂度往往与根号相关。
OI 中常见的数据结构题目：
- 区间修改……
- 区间查询……
这类题目往往可以用线段树、平衡树等经典的数据结构来解决，但传统的数据结构有代码难度大、常数大的劣势，对一些这类问题我们可以考虑对时间分治，但并不是所有问题都容易实现区间合并，这时就需要利用分块的思想，
常见的套路是：
假设有 $n$ 个元素，将连续的 $m$ 个元素分成一块，那么每次查询或修改时的区间一定包含最多 $\left\lfloor\frac{n}{m}\right\rfloor$ 个完整的段，和最多 $2m-2$ 个单点，我们对完整的段统一处理，对剩余的单点暴力处理。
那么只要选取合适的 $m$ ，在本例中就是 $\sqrt n$ ，设单点修改的复杂度为 $f(n)$ , 那么总复杂度就是 $O(nf(n)\sqrt n)$
[CodeChef] Chef and Churu
给定一个长度为 $n$ 的数字序列 $a$ ，和一个长度为 $n$ 的函数序列 $f$ ，每个函数都是 $f_i=\sum_{j=l_i}^{r_i}a_j$ 形式。
询问 $\sum_{i=l}^rf_i$ 的值；
修改 $a_i$ 的值。
$n\leq10^5,a_i\leq10^9$
首先，我们要对函数分块，记录每一块的初始答案，那么每次询问时求整块的答案，再加上两边不超过 $2\sqrt n$ 个函数的值，若能做到 $O(1)$ 查询函数值，那么只需要 $O(\sqrt n)$ 的时间复杂度。
那么问题就变成了如何$O(1)$ 查询函数值，其实不难：对数字序列也分块，维护每一块的块内前缀和，和每一块的之前的块的一个前缀和。
每次修改时，需要修改：
- 数字序列的两个前缀和，直接 $O(\sqrt n)$ 更新，以保证单个函数查询无误；
- 函数块的答案，需要预处理出没个函数快中的函数包含数字序列中的各个元素次数，共需要 $O(\sqrt n)$ 的时间复杂度，这样保证了整块函数值查询无误。
综上所述，查询和修改的时间复杂度都是 $O(\sqrt n)$ ，那么整个算法的时间复杂度就是 $O(n\sqrt n)$ .
1 |
|
##分类讨论
分块的思想本质上就是分类讨论：大块的个数少，小点修改起来块。
其实在很多应用分块思想的题目中并不是直接分块，而是应用了分块的分类讨论思想
###[TC SRM589 Div1] Flipping Bits
给定一个长度为 $n$ 的 01 字符串，每次操作可以将一个位置取反，或是将前 $k*m$ 个位置取反，问最少要多少次操作才能将原串变成一个长度为 $n-m$ 的前缀和长度为 $n-m$ 的后缀长度相等的串。
$n\leq300$
首先，题目中所谓”长度为 $n-m$ 的前缀和长度为 $n-m$ 的后缀长度相等的串“其实就是循环节为 $m$ 的循环串。
然后虽然不会证明，但不难发现这种题是不会有线性解法的（至少我不会）。所以只能枚举暴力，但是数据范围对 $O(2^n)$ 复杂度来说还是太大了，于是我们遵循题目中的暗示：分块。
其实就是分两种情况讨论：
- 当 $m\leq\sqrt n$ 时，直接枚举答案（循环节），这样的话再 DP 一下整段的翻转，转移的时候就加上需要的单点修改次数即可。
- 当 $m>\sqrt n$ 时，每一块都很长，但总数就少了，那么枚举每一段是否被翻转。注意到在每各个块中相对位置相同的元素一定要相同，那么就统计一下这些元素的 01 的数量，把少的改成多的就好。
1 |
|
定期（延时）重构
延时重构的思想很简单，就是每次询问单独处理复杂度太高，于是我们把一些询问分成一块，每次处理一个快内的询问。
##莫队算法
数论中的分块
由于数论的一些性质，许多题目可以用类似分块的做法处理。
[[51nod 1386] 双马尾机器人]
1 |
|