浅谈分块在信息学算法的应用

引语

在信息学奥赛或其他的算法应用中，我们常常会用到分治算法的思想来优化我们的程序。分治算法，顾名思义，就是“将一个规模为$N$的问题分解为$K$个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。[1]”。分块算法就是一种优秀的通过分治思想来优化的算法。分块算法不仅常数与线段树相比非常的小，而且块内可以嵌套其他数据结构，拓展性极强。

从基础中看分块

引题：

给出一个长为$n$的数列，以及$m$个操作，操作涉及区间加法，单点查值。
以下默认$n$是$10^5$级别的数。

分析：

这是一道能用许多数据结构优化的经典题，可以用不同数据结构来进行优化，比如说线段树：只要操作于询问区间能快速合并，只要操作与询问满足区间性质，线段树就可以以时间复杂度为$O(n\log n)$出色地完成这道题。

然而，线段树最明显的弊端就是代码太长、常数太大，若对于线段树不是很熟悉可能要调试很长时间才能调试出一个满意的结果。

这时，在数据不太大的情况下，我们可以用分块算法解决这个问题。

分块的初步介绍

分块算法，就是将一个序列中每$m$个元素打包成一个整体（块），这些块没有相交的部分，然后对这个整体进行维护，只记录这个整体的有关信息，这样当我们需要访问整个块中的元素时，我们可以直接把维护好的信息直接调用，已达到优化算法的目的。

比如说，对于一个数组$ai$，里面有初始值为$1,2,3,…,99,100$的$100$个数，现在我们要求找出第40个数的值，我们可以直接调用$ai[40]$，然而当我们需要区间修改第$a=32$个数到第$b=56$个数，使它们都加上$c=10$。如果使用朴素算法，我们需要直接从第$32$个数开始遍历每一个数到第$56$个：

void addUp_1(int a,int b,int c){
    //此处我们令a=32,b=56,c=10
    for(int i=a;i<=b;i++){
        ai[i]+=c;
    }
    return;
}

这个朴素算法的时间复杂度为$O(NM)$（$M$为查询次数）若a,b的范围足够大，在大量的修改和查询下，这个时间复杂度就有些不可接受。

这时我们可以使用分块算法，此处我们可以将$m=5$个元素分为一块，预先维护好块中所有元素的和，这样共把区间分为$\lfloor \frac{m}{n}\rfloor$个完整的块。对于一个查询，查询区间内有若干块完整的块，并且两侧还有不完整的块，这些块只有一部分包含于区间内，不能以整一块的方式来直接获取这一块的和。

若$m=5$，则区间被分为如下几块：

序号	1-5	6-10	……	96-100
区间中的每一个数作为整体编辑时的增加值（以下简称为“增加值”）	0	0	……	0
对应元素	1,2,3,4,5	6,7,8,9,10	96,97,98,99,100

对于上述的$a=32,b=56,c=10$的情况，我们可以将修改变成这样：

序号	32-35	36-40	……	51-55	56
增加值	0	10	10	10	0
对应元素在列表中的值	32 +10=42,33 +10=43,……,35 +10=45	36,37,38,39,40	51,52,53,54,55	56 +10=66

我们在对区间整体做加法操作时，涉及到了{31-35}、【36-40】、【41-45】……【51-55】、{56-60} 这些块。用“{}”注明的块因为不完全包括在区间内，所以我们要对这些元素进行逐一修改；但是对于用“【】”注明的块因作为一个整体被调用，所以我们可以不去逐一修改块中的每一个值，而是打上一个标记，注明区间中的每一个数作为整体编辑时的增加值，这样我们就可以省去了对于完整的块的逐一修改操作。对于一个点的值的查询，我们可以直接使用“块中记录的‘增加值’+自身在修改中被修改成的值”来求得单点的值。

分块的初步运用

搬寝室 [2]

一段走廊在一定时间内只允许一位同学通过（从$1$寝室到$5$寝室与从$2$寝室到$4$寝室是不能同时进行的；为了方便，从$1$寝室到$4$寝室与从$4$寝室到$5$寝室也是不能同时进行的；原寝室和目标寝室相同也是合法的）;

我们假定每次搬东西所需要的时间都为$1$.

求：从开始搬东西起，最少要经过多少时间他才能到绿茵场上。

数据规模：

对于$30\%$的数据，$N\leq 20,M\leq 20$
对于$60\%$的数据，$N\leq 2000,M\leq 2000$
对于$80\%$的数据，$N\leq 100000,M\leq 200000$
对于$100\%$的数据，$N\leq maxlongint,M\leq 200000$

对于这道题，我们可以发现，答案就是所有寝室被经过的次数中的最大值。此处重点是最大值的计算，所以此处将证明略过。[3]

对于此处的计算，我们定义两个数组stk[]（保存一个块的‘增加值’）和ss[]（保存具体的每一个数，用于不完整的块的逐一修改）。我们要一一修改的区间其实就是$[a , (\frac{a-1}{M+1})\times M]$ 和 $[(\frac{b-1}{M}) \times M+1,b]$，并且对于每一个数$i$，其对应的块的序号应为$\frac{i-1}{M}+1$，所以对于区间内的整块，我们可以直接修改$[\frac{a-1}{M}+2, \frac{b-1}{M}]$的块标记，最后再通过ans = max(ans,ss[i]+stk[(i-1)/DN+1]);求得最终的答案。

使用分块储存答案

简单的问题

统计$[a,b]$内素数的个数。
$1\leq a \leq b \leq 100000000$。

大多数人一开始的反应就是通过简单的素数筛来求出$[1,b]$内的所有素数然后加起来。先不说统计所有的素数时需要一个bool flag[100000001]，数组很大不一定满足题目的空间限制，而且在极端情况下，就算我们只是从$99999999$算到$100000000$，为了素数筛我们也要从2开始筛素数。这时候，我们可以事先维护好每一块区域内的素数和，然后在需要的时候直接调用。但是对于区间两边的不完整的块又该如何处理？我们可以把筛分成两部分，一部分用于筛出合适的因数，一部分用于在选定的范围内找出合适的数。

分多少块比较合适？

分块的数量会直接影响到分块的效率问题，如果每一块中的序列数量过大，那么对于两边的不完整的块逐一修改常数将会变大；而如果分块的数量太多，那么对于分块的处理常数也会变大。经过实验，当分的块数在$\sqrt{n}$时效率最高。

相关的数学证明引用了HeRaNO的《关于分块时间复杂度的证明》[4]：

分块的相关拓展

询问区间内小于某个值 $x$ 的元素个数

有了上一部分的经验，我们可以发现，数列分块问题实际上有三样东西需要我们思考：

不完整的块的$O(\sqrt{N})$个元素怎么处理？
$O(\sqrt{N})$个整块怎么处理？
要预处理什么信息（复杂度不能超过后面的操作）？

我们先来思考只有询问操作的情况

不完整的块： 枚举即可。
整块： 要在每个整块里寻找小于$x$的元素数量时，我们不得不要求块内元素有序，这样我们可以通过二分法对块内排序。

我们可以进行如下预处理：将所有分好的块内部进行快速排序，复杂度$O(n\log \frac{n}{m})$，每次查询需要在$\frac{n}{m}$个块内使用二分法，在不完整的$2m$个元素里直接枚举求解。

这样总的复杂度为$O(n\frac{n}{m}\log \frac{n}{m}+nm)$，如果$m=\sqrt{n}$的话，总复杂度为$O(n\sqrt{n}\log n)$，在实际测试时$m$取$2\sqrt{n}$左右时效果更好。

如果算上区间加，维护一个标记$tag$，对于不完整的块需要逐一枚举并且重新排序，复杂度略；对于完整的块，二分查询小于$x-tag$的元素个数。

询问区间内小于某个值 $x$ 的前驱（比其小的最大元素）

接着上一个部分的解法，其实只要把块内查询二分稍作修改，对于一个块保留块内的前驱，最后一起比较即可。

在块内插入其他数据结构

上一部分实际上具有一个启发意义：可以在块内维护其他的数据结构使其更具有拓展性，比如对于查找“比其大的最小元素”，在分好的块内放一个$STL$中的set，这样我们可以直接调用upper_bound()来查询，降低时间复杂度。

区间加法，区间求和

这一部分不完整的块还是枚举求解，不过我们可以对完整的块进行预处理求和，用类似于标记的做法，直接根据块内元素计算增量。

结语

综上所述，分块算法拥有常数小、可拓展性强等优点，虽然分块算法相对于其他算法解决特定问题时间复杂度可能相对较劣，但是嵌套其他数据结构等方法可以让分块从一个朴素的根号算法升格为一个通用性的解题方法。

备注：

文章中引用的参考文献及相关备注

分治算法定义 (https://baike.baidu.com/item/分治算法/3263297)
后山OnlineJudge P1400 搬寝室 (move) (https://oj.zhtg.red/p/1400)
证明其实也不复杂，经过同一个寝室的任务不能同时进行，所以完成所有经过次寝室的任务至少要过其被经过的次数个单位的时间。
HeRaNO 分块的复杂度证明 (https://blog.csdn.net/HeRaNO/article/details/55219560)

致谢及其他参考文献：

感谢hzwer在该课题上对我的启发和指导，感谢李建江、班轩等各位竞赛教练对我的培育与支持。

罗剑桥《浅谈分块思想在一类数据处理问题中的应用》

董永建董欣然等《信息学奥赛一本通·提高篇》

搬寝室相关代码：

#include<bits/stdc++.h>
#define DN 632
using namespace std;
int stk[700],ss[400005],n,m,cnt=0,ans=0;
long long a,b,tmp,s[400005],r=0,rr=1;
pair<long long,long long> pi[200005];
map<long long,int> pp;
int main(){
    scanf("%d%d",&n,&m);
    //数据的初始化
    for(int i=1;i<=m;i++){
        scanf("%lld%lld",&a,&b);
        if(a>b) swap(a,b);
        pi[i]=make_pair(a,b);
        s[++r]=a;s[++r]=b;
    }
    sort(s+1,s+r+1);
    //离散化处理
    while(rr<=r){
        while(s[rr-1]==s[rr])rr++;
        if(rr>r)break;
        pp[s[rr]]=++cnt;
        rr++;
    }
    for(int i=1;i<=m;i++){
        a = pp[pi[i].first];
        b = pp[pi[i].second];
        //对于长度小于2n的区间可以直接枚举
        if(b-a+1<=DN*2){
            for(int j=a;j<=b;j++){
                ss[j]++;
            }
        }else{
            //对于区间左边的不完整块的处理（枚举）
            for(int j=a;j<=((a-1)/DN+1)*DN;j++){
                ss[j]++;
            }
            //对于完整块的处理（打标记）
            for(int j=(a-1)/DN+2;j<=(b-1)/DN;j++){
                stk[j]++;
            }
            //对于区间右边的不完整块的处理（枚举）
            for(int j=((b-1)/DN)*DN+1;j<=b;j++){
                ss[j]++;
            }
        }
    }
    //最终处理
    for(int i=1;i<=cnt;i++){
        ans = max(ans,ss[i]+stk[(i-1)/DN+1]);
    }
    printf("%d\n",ans);
    return 0;
}

引语

从基础中看分块

引题：