块状数据结构学习笔记

分块

分块的思想和珂朵莉树很类似，就是把原序列分成若干个块，对块进行操作的奇妙思想。复杂度通常带根号。分块的块长也有讲究，通常对于大小为 $n$ 的数组，取距离 $\sqrt{n}$ 最近的 $2$ 的幂数或直接取 $\sqrt{n}$ 即可，如果 TLE 了可以考虑把块长乘 $2$ 或除以 $2$。

数列分块

最简单的分块。基本上分两步走，对于一个操作的区间 $[l,r]$，如果刚好在某个块区间内，直接暴力修改 $[l,r]$ 的值；如果横跨多个区间，先处理整块，然后处理边角料。

常用操作如下：

1. 区间加法、单点查询

   最简单的数列分块操作，具体详见代码：

   #include <bits/stdc++.h>
   using namespace std;
   #define int long longconst int maxn=5e4+5;
   int n,opt,ll,rr,cc,len,a[maxn],id[maxn],tag[maxn];void add(int l,int r,int c)
   {int sid=id[l],eid=id[r];if(sid==eid)for(int i=l;i<=r;i++)a[i]+=c;else{for(int i=l;id[i]==sid;i++) a[i]+=c;for(int i=sid+1;i<eid;i++) tag[i]+=c;for(int i=r;id[i]==eid;i--) a[i]+=c;}
   }signed main()
   {cin>>n;len=sqrt(n);for(int i=1;i<=n;i++) cin>>a[i],id[i]=(i-1)/len+1;for(int i=1;i<=n;i++){cin>>opt>>ll>>rr>>cc;if(!opt) add(ll,rr,cc);else cout<<a[rr]+tag[id[rr]]<<endl;}return 0;
   }
   

2. 区间加法、区间求和

   块长同样是 $\sqrt{n}$，由均值不等式可知此时单词操作的时间复杂度最优，为 $O(\sqrt{n})$。预处理每一个块的区间和 $s$。

   对于区间 $[l,r]$ 的查询操作，考虑几种情况：

   • 若 $l$ 和 $r$ 在同一个块内，暴力统计，最坏时间复杂度为 $O(\sqrt{n})$；
   • 若 $l$ 和 $r$ 不在同一个块内，暴力统计不完整的块，直接累加完整的块的区间和，最坏时间复杂度为 $O(\sqrt{n})$。

   对于区间 $[l,r]$ 的加法操作，同样按照上面的思考方式：

   • 若 $l$ 和 $r$ 在同一个块内，暴力修改区间即可，最坏时间复杂度为 $O(\sqrt{n})$；
   • 若 $l$ 和 $r$ 不在同一个块内，暴力修改不完整的块同时更新 $s$，直接修改完整块的 $s$，最坏时间复杂度为 $O(\sqrt{n})$。

   代码如下：

   #include <bits/stdc++.h>
   using namespace std;
   #define int long longconst int maxn=50005;
   int a[maxn],id[maxn],tag[maxn]/*区间直接打标记*/,c,s[maxn],len;void add(int l,int r,int v)
   {int sid=id[l],eid=id[r];//start-id,end-idif(sid==eid) for(int i=l;i<=r;i++) a[i]+=v,s[sid]+=v;else{for(int i=l;id[i]==sid;i++) a[i]+=v,s[sid]+=v;for(int i=r;id[i]==eid;i--) a[i]+=v,s[eid]+=v;for(int i=sid+1;i<eid;i++) tag[i]+=v,s[i]+=len*v;}
   }int query(int l,int r,int mod)
   {int sid=id[l],eid=id[r],ans=0;if(sid==eid) {for(int i=l;i<=r;i++) ans=(ans+a[i]+tag[sid])%mod;return ans;}else{for(int i=l;id[i]==sid;i++) ans=(ans+a[i]+tag[sid])%mod;for(int i=r;id[i]==eid;i--) ans=(ans+a[i]+tag[eid])%mod;for(int i=sid+1;i<eid;i++) ans=(ans+s[i])%mod;return ans;}
   }signed main()
   {int n;cin>>n;len=sqrt(n);for(int i=1;i<=n;i++) cin>>a[i],id[i]=(i-1)/len+1,s[id[i]]+=a[i];while(n--){int opt,l,r;cin>>opt>>l>>r>>c;if(!opt) add(l,r,c);else cout<<query(l,r,c+1)<<endl;}return 0;
   }
   

块状数组