分块算法

Published: August 18, 2020 by Daltao

• Categories:
• algorithm 101

• Tags:

• 分块技巧
• 树上分块
• 分块和分治

分块技巧

假设给我们一个长度为n的数组，要求支持区间更新，区间统计。

最简单的方式是将数组分块，每一块大小为$m=\sqrt{n}$。之后我们为每一块都额外维护一份辅助信息，第i块的辅助信息记作$f(i)$。

现在考虑区间更新问题，只要利用惰性标记就可以实现$\sqrt{n}$的时间复杂度。对于完全处于区间中的块，我们直接标记在辅助信息上（如果已经有标记了，就合并标记），这样的块最多有$\sqrt{n}$个。而对于与区间有交集的却不被完全覆盖的块，我们先下推标记，之后直接暴力修改，可以得知这样的块不会超过两个，总的修改的元素不超过$2\sqrt{n}$个。

查询操作也是相同的，对于被完全覆盖的块，直接从辅助信息中提取，否则直接暴力查询，时间复杂度为$O(\sqrt{n})$。

题目1：给定$n$个数$a_1,\ldots,a_n$，要求处理$m$个请求，请求分两类：第一类某个区间加上一个数$x$（允许为负数）。第二类查询区间中小于$x$的数的数目。（其中$x$不同请求可能不一样），$n,m\leq 10^5$。

这个问题可以对数组进行分块，设$B$为每块的大小。之后对于修改操作，中间的区间打标记，两端的区间暴力更新（合并两个有序区间可以线性完成），因此修改请求的时间复杂度为$O(\frac{n}{B}+B)$。而对于查询请求，中间的用二分查找法，两端的暴力查找，时间复杂度为$O(2B+\frac{n}{B}\log_2B)$。

因此时间复杂度的上限为$m(B+\frac{n\log_2B}{B})$，我们可以选择$B=\sqrt{n\log_2B}$，则每个请求的时间复杂度为$\sqrt{n\log_2B}$，总的时间复杂度为$O(m\sqrt{n\log_2B})$。

实际上这个问题还可以用Fractional Cascading的技术，优化到$O(m\sqrt{n})$，但是由于实现复杂，很可能常数会大于$\sqrt{\log_2n}$。

提供一道题目。

题目2：给定$n$个数$a_1,\ldots,a_n$，要求处理$m$个请求。请求分为两类：第一类请求要求将区间$[l,r]$中所有大于等于$x$的数全部减去$x$，第二类请求查询区间$[l,r]$中有多少数正好等于$x$（不同请求的$x$可以不同）。满足$1\leq n,m,a_i,x\leq 10^5$。

我们可以按$B$对数组进行分块，并记录一个数组$L$，其中$L(i,j)$代表第$i$块中值恰好为$j$的所有数组成的链表。

先考虑查询操作，两端的区间暴力处理即可，时间复杂度为$O(B)$。而中间的每个区间，我们可以直接查表$O(1)$得出结果，因此总的时间复杂度为$O(B+\frac{n}{B})$。

在考虑修改操作，两端的区间暴力处理，时间复杂度为$O(B)$。而中间的区间，我们记区间中的最大值为$k$。

• $2x\leq k$，我们可以暴力查表找出所有小于$x$的数，并将其增加$x$。之后我们给整个块打上一个减$x$的标记。（这时候最大值为$k-x$）
• $2x > k$，我们可以暴力查表找出所有大于等于$x$的数，并将其减去$x$。

对于第一个操作，我们每查找一个数，最大值都要减少1。而对于第二个操作，最大值减少的量不少于我们查找数的数目。因此对于每个块，我们可以断定扫描次数一定不超过这个块中的最大值。记所有数的最大值为$M$，那么扫描的总次数不超过$M\frac{n}{B}$。

综合上面所说的，时间复杂度为$O(mB+\frac{nm}{B}+\frac{nM}{B})$。这里我们可以记$N=\max(n,m,M)$即可得到$O(N\sqrt{N})$时间复杂度。

一道题目。

树上分块

题目1：给定$n$个顶点组成的树，第$i$个顶点上写着一个数字$a_i$。令顶点$1$作为根。现在给出$q$个请求，每个请求指定两个顶点$u,v$，其中保证$u$是$v$的祖先。这时候给$u$到$v$路径上任意顶点分配权重，顶点$x$的权重为$a_x\oplus dist(v,x)$，对于每个请求，找出$u$与$v$决定的唯一路径上，最大的顶点权重。其中$1\leq n\leq 6\times 10^4$，$0\leq a_i\leq n$，$1\leq q\leq 2\times 10^5$。

发现所有涉及的数最多只有16位（二进制），我们可以将每个数拆解为高8位和低8位。预处理出数组$dp(v,i)$，记$A$表示所有顶点$v$的祖先中距离顶点$v$小于$2^8$的顶点组成的集合，则$dp(v,i)=\max_{u\in A} a_u\oplus dist(u,v)\oplus (i\cdot 2^8)$。

我们一旦计算出$dp(v,i)$，对于每个请求，我们可以从路径底部每次向上跳$2^8$距离，如果距离顶部小于$2^8$，则暴力计算。因此一次请求的处理时间复杂度最多为$\frac{6\cdot 10^4}{2^8}+2^8\leq 2^9$。请求处理的总时间为$O(2^9q)$。

那么该如何计算$dp(v,i)$呢，最简单的暴力计算方法就是枚举所有满足条件的祖先，这样处理每个顶点的时间复杂度为$O(2^{16})$，有点大。但是可以发现$dp(v,i)$与$dp(v,j)$的区别仅在于前者拿$a_u\oplus dist(u,v)$亦或上$i\cdot 2^8$，后者亦或上$j\cdot 2^8$。因此我们可以对一个顶点同时计算其相关的所有dp状态，用二叉树进行维护，这样时间复杂度就为$O(8\cdot 2^{8})$。

总的时间复杂度为$O(8\cdot 2^8n+2^9q)$。

分块和分治

这里讲一类可以通过分块和分治解决的问题。考虑这样一个问题：

给你两个序列$a_1,\ldots,a_n$和$b_1,\ldots,b_n$，要求你计算$\max_{1\leq i\leq j\leq n}bitcount(a_i\land b_j)$。这里$bitcount$计算一个整数二进制中的1的数目，而$\land$表示二进制且运算。其中$1\leq n,a_i,b_i\leq 10^5=M$

一般有$i\leq j$这样的条件的问题，都需要用到分治算法，在计算时消除$i\leq j$带来的复杂度。具体做法就是二分后，对左右两部分独立计算，计算完后再讨论左右两边对结果的影响。

一般问题到这里也就结束了，但是上面的问题的合并的过程中，我们需要借助到FWT算法，而FWT算法是和值域有关而与你数据量关系不大的。因此假如真的直接使用分治，算法时间复杂度将达到$O(nM\log_2M)$。

我们这里可以将整个序列分成$k$块，每块大小为$\frac{n}{k}$。对于每一块，我们用暴力算法计算。之后我们对这些块进行分治，而分治树上仅有$O(k)$个顶点，因此总的时间复杂度为$O(\frac{n^2}{k}+kM\log_2M)$。

在最坏的情况下$n=M$，因此结果为$O(\frac{n^2}{k}+kn\log_2n)$，取$k=\sqrt{\frac{n}{\log_2n}}$，此时结果为$O(n\sqrt{n\log_2n})$。