本文主要记录了我做题时对分块算法的一些感觉。
分块在处理一些奇奇怪怪的区间处理问题时常常十分有用。
普通线性分块——以区间加法为例
问题1：给出一个长度为$N$的序列，共有$M$个操作，操作为区间加法或者区间求和。
考虑将序列分成$T$块，每一块长均为$S = \frac{N}{T}$，然后处理一系列的操作。
对于区间加法，我们分两种情况：
- 若目标区间长度不足一个块，则对区间内每一个元素进行暴力修改。
- 若区间跨了多个块，那么对区间内的所有完整的块进行遍历，依次打上加法标记；对于区间端点所在的两个块，只对其中在区间内的元素进行暴力修改，换言之，对左右两端两个不完整的块进行暴力修改。
对于区间求和，同样分两种情况： - 若目标区间长度不足一个块，则对区间内每一个元素进行暴力统计。
- 若区间跨了多个块，那么对区间内的所有完整的块进行遍历，依次累加上它们的和；对于区间端点所在的两个块，只对其中在区间内的元素进行暴力统计，换言之，对左右两端两个不完整的块进行暴力统计。
这么做的时间复杂度是$O(M(S+T))$。根据均值不等式，当$S=T=\sqrt{N}$时括号内的值最小。因此选择的块数和块长都为$\sqrt{N}$时可以做到理论上的时间复杂度最优。
打标记的做法和线段树相似，因此扩展到区间乘法，区间赋值的时候可以依照线段树的规则进行扩展，原理则基本相同。
事实上，这种分块方式是最常见的。有时会根据具体的算法调整块的大小已达到理论最优时间复杂度。
特殊线性分块1——使用特殊方法（数据结构）维护块
问题2：题目链接
考虑分块，发现区间加法虽然好做，但是求区间有多少个满足条件的人是不好办的，只有序列有序的时候才可以用二分这样时间复杂度稍低的方法求出答案，但在执行了区间加法后有序性就有可能被破坏。
继续观察可以发现，分块后区间加法导致有序性被破坏的情况只有“区间加法没有覆盖完整的一块”这一种情况。因此事先对每一个块内部排序，区间加法除按照之前所述方法进行外，还要对不完整的块打上一个“有序性破坏”的标记。区间查询时，对有序性存在的完整块直接二分出答案，对有序性被破坏的完整块先排序再求解，对不完整的块暴力统计。
因为一个区间加法最多导致2个块的有序性被破坏，所以排序的总次数为$O(\sqrt{N} + Q)$，总时间复杂度为$O(n\log n + q \sqrt{N} \log n)$。
在这类问题中，某些操作不能使用打标记之类的简单，普适的方法去解决时，就可以考虑用其他一些高明的方法（在本题中表现为排序，有时也表现为用数据结构维护块）——毕竟分块本身就算的上是一种相当高明的暴力方法嘛。（当然，要看数据规模）
特殊线性分块2——块状链表和暴力重构
问题3：题目链接
这个题目像是NOI2003 文本编辑器的弱化。事实上这个题目是可以用块状链表实现的，但因为这里是分块的讲解，所以还是考虑分块。
由于本题的操作比较简单，就只有插入，所以可以直接用一个链表来模拟。将链表分成$O(\sqrt {N})$段，每一段都保存段的长度（因为段会因为插入而变长）和段的开头，在理想情况下可以利用长度在$O(\sqrt {N})$时间内找到插入的位置并且完成插入。询问同理。这样总时间复杂度就是$O(N\sqrt {N})$。
但是数据经过特殊构造后可以形成一个段特别长的情况，此时分块链表退化成为普通链表，时间复杂度最坏会达到$O(N^2)$。为了避免这种情况，需要在插入达到一定次数之后及时对链表进行重构，即重新分块。令插入次数的限制为$O(\sqrt {N})$，因为重构花费的时间是$O(n)$，而每次重构之后插入的时间复杂度都会恢复为原来水平，因此重构+插入+询问的总时间复杂度就是$O(N\sqrt {N})$。
这类问题一般有着大量的插入和删除操作，对应的是链表这样能够快速执行插入和删除的链状结构，因此使用有着分块思想的块状链表可以快速准确的完成这些操作。同时当操作简单时直接对所有的块进行重构也是一个不错的选择。