分块思想小结

关于分块思想的一点点理解和总结

主要思想是通过把某一维东西分成若干块（下标/值域/操作时间/etc），通过在较为均衡的时间内维护整块、散块或是某些题中一些特定的信息，从而达到修改和查询/预处理和查询的时间复杂度的平衡。

具体来说，往往是通过降低复杂度较高/操作次数较多部分的复杂度，提升复杂度较低/操作次数较少部分的复杂度来达到平衡的目的

需要注意的是，分块不一定都是分成$\sqrt n$块，需要根据具体题目计算复杂度，算出最优块大小。不过我们一般直接测试实际运行时间，手动调整块大小。

实现过程

把问题规模$n$分成$k$块，每块大小为$\frac{n}{k}$

微观来看，每个块花费$f(\frac{n}{k})$时间；宏观来看，$k$个块花费$g(k)$时间

找到$k$满足$f(\frac{n}{k})=g(k)$，此时复杂度最优

几类经典问题

最基础的分块

给一个长度为$n$的序列$a[]$，支持以下操作：

1. 令$a[x]=y$
2. 计算$\sum_{i=l}^{r} a[i]$

Solution

有两种解决方法：

• $O(1)$修改，$O(\sqrt n)$查询

  记录每个整块内部的元素和

  修改直接修改原序列以及所在块的元素和，查询直接暴力跳整块、计算散块

• $O(\sqrt n)$修改，$O(1)$查询

  记录整块的元素和的前缀和，再预处理出每个块内的前缀和

  修改时暴力修改所有前缀和（所有整块的以及所在整块内的），直接利用前缀和$O(1)$查询

根据实际情况选择更优方法

$\pm 1$RMQ

求相邻元素相差恰好为$1$的序列的RMQ，复杂度$O(n)-O(1)$

Solution

考虑分块，分成$k$块，用ST表处理出两两整块之间的最小值，且预处理出每个块内的前后缀和

感性理解一下，这个时候$k$取越大越好

但是不难发现，这样做会存在一个问题，如何计算询问端点全都落在某一整块内的答案？

由于$\pm1$这个性质，不难发现把每个块内的元素减掉这个块第一个元素的值后，所有的整块内最多只有$O(2^{\frac{n}{k}})$种可能性（这里感性理解一下可能的情况是很少的，具体大小下面有写）。预处理出所有可能数列的所有最小值的出现位置。复杂度是$O\big(2^\frac{n}{k}(\frac{n}{k})^2\big)$

预处理+查询的总复杂度是$O(k\log k+m)$的

令两者相等，求出$k=\frac{n}{\log(\frac{n}{\log^2n})} = \frac{2n}{\log n}$，此时复杂度是$O(n+m)$

区间众数

可以通过莫队做到$O(n\sqrt m)$，注意不用数据结构维护，直接开个桶，暴力更新最大值即可

考虑如何用分块在线做

依旧设分成$k$块，考虑计算$num[x][y]$表示$x$这个数在前$y$个块里的出现次数，这可以$O(nk)$预处理（先处理出第$y$个块的，再扫一遍求前缀和）

紧接着，我们就能求出任意两个整块中间这段区间的众数了（对于每个左端点往右扫一遍，用一个桶记录出现次数）

对于一个询问$[l,r]$答案要么在中间连续的整块中，要么在散块的前缀/后缀中

最后有可能成为答案的数只有$O(\frac{n}{k})$个（中间一个，两边散块长度$O(\frac{n}{k})$）

暴力枚举这些数，还是用一个桶计算可能的数的出现次数，扫一遍即可

当$k=\frac{n}{\sqrt m}$时，最优复杂度为$O(n\sqrt m)$

更一般的模型/思想

长度为$n$的序列，有$m$次询问。暴力查询是$T(n,m)$的

Solution

分$k$块，每块$\frac{n}{k}$个，查询变成每次$T(\frac{n}{k},m)$的了

总复杂度$k*T(\frac{n}{k},m)$

---

举个例子，$T(n,m)=O(n^2+m)$时，$k=\frac{n}{\sqrt m}$有最优复杂度$O(n\sqrt m)$

基于操作时间的分块

长度为$n$的序列，有$m$次操作（修改或询问），暴力复杂度$T(n,m)$

Solution

把操作序列分成$k$块，每块$\frac{m}{k}$个，每个块暴力操作需要花费$T(n,\frac{m}{k})$的时间

在处理完每个块之后，整体应用这些操作的复杂度为$B(n,k)$

总复杂度为$k*\big(T(n,\frac{m}{k}) + B(n,k)\big)$

---

一个例题：

$n$个点的树，$m$次操作：

1. 标记$x$这个点
2. 找$x$与其最近的被标记点的距离

这里只考虑分块做法

此时$T(n,m)$的暴力做法就是对于每个询问，答案要么是以前已经在之前块内处理完的答案，要么是当前块内在它前面的修改

$B(n,m)$的做法就是用bfs$O(n)$重新计算每个点到最近被标记点的距离

---

最后，分块还有一些比较套路的操作（如值域分块查区间第$k$大等），但由于我比较懒思想都比较类似，就不赘述了