分块简单入门

按

树状数组虽超级快，但是很僵硬，不灵活；线段树虽快，但是却不直观，代码量大；所以，速度较慢但直观形象、代码量小的分块大法不实为线段树的替代品。

网络上关于分块的教程不知道为什么很少，虽然早有hzwer大神的，但是还是少了入门级详解教程。此篇将分为三个阶段，保证初学者在有意识地阅读后基本掌握分块。

1.简单的入门题

问题引入

给定长度为N(N<=1e5)的正数数列A，然后输入Q(Q<=1e5)行操作命令，指令形如Q l r，表示统计数列中第l~r个数中的最大值

思路

首先想到的简单暴力遍历在这个数量级是会超时，这道题我们可以用分块来做。

先将长度为n，从1开始标号的数组a分为 sqrt(n)块（此时时间复杂度最小）维护，那么易得以下推论

• a[i]处于(i-1)/sqrt(n)+1块
• 第i块的左端点为(i-1)*sqrt(n)+1，右端点为min(i*sqrt(n), n)

以上推论便于理解后续实现，可以自己动手模拟验证一下

我们可以先预处理出每一块的最大值并存入数组m[]中，于是对于命令Q l r，我们可以将查询区间[l,r]分为两个部分——所有的整块（整区间）部分和开头和结尾不足一整区间的部分。然后对于整区间我们直接取已维护好了的区间最大值m[i]进行比较，而对于开头和结尾不足一整区间的部分，我们朴素暴力遍历，最终合并答案，得解。

这便是分块算法最基本的思路，概括起来就是大段维护，局部朴素

实现

说明：

blo为区间大小，pos[i]表示a[i]元素位于第pos[i]块，其他变量名同上

例码：

#include 
    
     #include 
     
      #define MAXN 100001#define MAX(a,b) ((a)>(b)?(a):(b))//宏#define MIN(a,b) ((a)<(b)?(a):(b))using namespace std;int blo,n,q,a[MAXN],m[MAXN],pos[MAXN];int query(int l, int r){    int ans=0;    for(register int i=l;i<=MIN(r, pos[l]*blo);i++)//统计左区间（或者查询区间）        ans=MAX(ans, a[i]);    for(register int i=pos[l]+1;i<=pos[r]-1;i++)//统计整块区间        ans=MAX(ans, m[i]);    if(pos[l]!=pos[r])//如果存在右区间才遍历，防止重复计算        for(register int i=(pos[r]-1)*blo+1;i<=r;i++)//统计右区间            ans=MAX(ans, a[i]);    return ans;}int main(){    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);//输入输出加速    cin>>n;    blo=sqrt(n);    for(int i=1;i<=n;i++)           cin>>a[i],pos[i]=(i-1)/blo+1,m[pos[i]]=MAX(m[pos[i]], a[i]);//初始化    cin>>q;    char type;    int l,r;    while(q--){        cin>>type>>l>>r;        cout<
      
       <
      
     
    

2.较难的区间修改

问题引入

给定长度为N(N<=1e5)的数列A，然后输入Q(Q<=1e5)行操作命令

• 第一类指令形如C l r d，表示把数列中第l~r个数都加d
• 第二类指令形如Q l r，表示统计数列中第l~r个数的和

思路

同样如上，将长度为n，从1开始标号的数组a分为 sqrt(n)块维护

然后对于操作命令C l r d，[l,r]开头和结尾不足一整区间的部分暴力操作并维护区间之和sum[]；而[l,r]包含的所有整区间则不用暴力操作，而是使用一个add[]数组（类似于线段树的lazy[]延迟标记）记录操作值。

对于命令Q l r也就同理，不足一整区间的部分暴力相加并再加上add[]标记乘以当前区间的个数（因为为了分块算法的效率，操作整块区间时并没有真的修改区间内元素所有值，而是直接用延迟标记add[]暂时记录下来，所以当后面再单独操作取值时，就必须下放延迟标记）；而整块部分则直接sum[]相加即可

总体时间复杂度为

\[ O((N+Q)*\sqrt[]{N}) \]

实现

例码：

#include 
    
     #include 
     
      #include 
      
       #define MAXN 100010using namespace std;int n,q,a[MAXN],blo,sum[MAXN],add[MAXN],pos[MAXN];void change(int l, int r, int d){    for(register int i=l;i<=min(pos[l]*blo,r);i++)        a[i]+=d,sum[pos[l]]+=d;    for(register int i=pos[l]+1;i<=pos[r]-1;i++)            add[i]+=d;    if(pos[l]!=pos[r])//防止重复计算        for(register int i=(pos[r]-1)*blo+1;i<=r;i++)            a[i]+=d,sum[pos[r]]+=d;}int query(int l, int r){    int res=0;    for(register int i=l;i<=min(pos[l]*blo,r);i++)        res+=a[i]+add[pos[l]];    for(register int i=pos[l]+1;i<=pos[r]-1;i++)        res+=sum[i]+add[i]*blo;    if(pos[l]!=pos[r])//防止重复计算        for(register int i=(pos[r]-1)*blo+1;i<=r;i++)            res+=a[i]+add[pos[r]];    return res;}int main(){    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);//输入输出加速    cin>>n;    blo=(int)sqrt(n);    for(int i=1;i<=n;i++)        cin>>a[i],pos[i]=(i-1)/blo+1,sum[pos[i]]+=a[i];//初始化    cin>>q;    char type;    int l,r,d;    for(int i=0;i
       
        >type>>l>>r;        if(type=='C'){            cin>>d;            change(l,r,d);        }else            cout<
        
         <
        
       
      
     
    

扩展

其实本题的操作还可以包含区间乘法，即操作涉及区间加法、区间乘法，n个区间和询问。具体思路就是开两个标记数组，分别维护区间加法和区间乘法。值得注意的是，每一次下放标记时，乘法的运算优先级要高于加法，比如当前块加法标记已为m，那么再进行一个乘n的操作后，加法标记应更新为n*m

3.难题

问题引入

思路

在线分块大法，首先离散化一下，然后预处理出m[a][b]数组，表示第a块到第b块中蒲公英出现次数最多的编号为m[a][b]；在查询区间[l,r]时，采用分块思想，整区间直接取出与首尾暴力得到的答案进行合并，得解。

实现

（在洛谷上没开O2就RE，开了O2就AC了，也不知道为什么(；´д｀)ゞ）

// luogu-judger-enable-o2#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
        
       
      
     
    

参考

• 《算法竞赛进阶指南》

本文采用 进行许可。欢迎转载，请注明出处： 转载自：