update: 2023/12/12 fixed pictures
update: 2025/02/12 fixed KaTeX
本文中所有图片均使用Power Point制作
基本分块#
俗话说得好：
\(\Huge 暴力+暴力=分块\)
分块总的来说就是线段树的阉割版，其时间复杂度基本维持在 \(\sqrt N\) 数量级。一般的分块支持单点/区间查询以及单点/区间修改.
分块的块长一般是 \(\sqrt N\) （ \(N\) 是数组大小），例如，对于一个数组 \(A\) ， \(|A|=13\) ，每一块的长度便是 \(\sqrt {13}\approx3\) ，但是分块完成后我们会发现最后一块的大小是 \(1\) ，不足其他块的大小（如下图）.
区间修改区间查询#
分了块后我们便可以干很多事了，单点查询/修改就不说了，直接访问数组下标进行修改.我们来说说区间查询/修改，例如还是那个数组 \(A\) ，现在我们要修改下标为 \(2\) 到 \(7\) 的区间，这个时候我们要对每一块生成一个懒标记，于是我们的思路便很明确了，对于这段区间里整块的部分直接修改懒标记，剩下的不足一整块暴力修改（如下图）.同理，查询也是一样，只是要注意统计时要把所有懒标记加上，不管是整块还是不足整块.下面是一道区间加法，单点查值的题目：数列分块入门1.
动态区间第 \(K\) 小#
分块的大部分题目并不像这样简单，例如下面的动态区间第 \(K\) 小数例题.
给定一个由 \(N\) 个数组成的序列 \({A_1,A_2,…,A_N}\) 每次可以将 \(A_k\) 的值改为 \(t\) ，或者提问序列中 \({A_l,..,A_r}\) 中第 \(k\) 小的数的值.
对于这道题，我们需要使用另一个数组
\(B\) 用来将每个块内的元素排序，需要查询时先使用二分答案，再在 check() 内对于整块的统计答案直接使用排序的数组进行二分，正所谓一个分块套二分再套二分，细节很多，详见Dynamic Ranking（在这道题只能拿
\(50\) 分）.
带多个懒标记的分块#
除此之外，还有要同时开两个 lazy 的题目——数列分块入门7，关键在于处理两个运算法则之间的优先级.
数列分块入门5——在根号开到一定程度时块内的元素会全部变为 \(1\)，这时可以不用暴力统计，直接计算块长.
块状链表#
另外，还有一类分块题，算是属于半个块状数组（或者说块状链表）.
众所周知，数组访问时间复杂度 \(O(1)\) ，修改 \(O(n)\) ，而链表访问 \(O(n)\) ，修改 \(O(1)\) .
而块状链表，就是两者的结合体，它查询 \(O(\sqrt n)\) ，修改 \(O(\sqrt n)\) ，两者时间复杂度相差不大，是个折中方案，具体长什么样见下图.
那我们应该如何维护来保证它们的时间复杂度呢？很简单，我们只需要在一个块的大小大于一定的值后暴力拆分成两块接在原块后面，具体来说，我们要在一块的大小大于 \(2\sqrt N\) 时分裂（注意：此处的 \(N\) 指的是所有元素，包括了后面新增的元素，也就是说每次添加元素时要重新计算阈值长度）.理清思路后，上例题：数列分块入门6.
莫队#
除了一般的分块题和块状链表外，分块还有一个重要作用——莫队，它可以解决一部分的区间查询题目(尤其是查询某种区间有几种值的).
先说本质，本质并不是分块，而是双指针.莫队在运行时会用到两个数组，一个是原来的数组，另一个是 cnt 数组，cnt 数组是用来记录每个数出现的次数(在某些时候可能需要配合离散化食用).下面是算法基本的运行过程.
首先我们有两个指针 i 和 j ，先不考虑为什么他们在这个位置上，现在我们要把他们移到既定位置.我们有一种很简单的思路，先把左（ i ）移到既定位置的左端点，再把右（ j ）移到既定位置的右端点上.而在这个期间，我们可以顺便统计 cnt 数组，并且维护 tot 变量（统计种类，具体来讲是在 cnt 某个值从
\(0\) 到
\(1\) 或是从
\(1\) 到
\(0\) 的过程中修正）.于是我们就有了一个基本的模型了，就是不断通过移动双指针来处理每个询问，但是很明显，这样移来移去，i 最多会移动
\(MN\) 次（
\(M\) 是询问次数，
\(N\) 是数组长度），j 也同理，这样的时间复杂度是不行的.而莫队算法就是在此处做了优化.
不带修版本#
莫队首先会把询问离线，并把数组的点进行分块，而排序询问的第一关键字是每个询问左端点所在块的编号，而第二关键字是右端点.具体实现见小 Z 的袜子.
带修版本#
除此之外，莫队还有一种带修改版本.
不是说了将询问离线了吗，离线处理时怎么修改啊.
还是可以修改的，现在带修改功能得将修改的点还原到询问前的状态.
现在时间也得移来移去了.
嗯？时间移来移去？像
i和j那样？那这就好实现了啊.新增一维来处理时间.
具体怎么讲？
记录一下每次修改前后的状态，每次将时间移动时便一步步更换状态，直到回溯到指定时间，同时
cmp函数也要改一下.
于是，我们就有了 数颜色 / 维护队列 的代码.