分塊

分塊的思想和珂朵莉樹很類似，就是把原序列分成若干個塊，對塊進(jìn)行操作的奇妙思想。復(fù)雜度通常帶根號。分塊的塊長也有講究，通常對于大小為 $n$ 的數(shù)組，取距離 $\sqrt{n}$ 最近的 $2$ 的冪數(shù)或直接取 $\sqrt{n}$ 即可，如果 TLE 了可以考慮把塊長乘 $2$ 或除以 $2$。

數(shù)列分塊

最簡單的分塊?；旧戏謨刹阶?#xff0c;對于一個操作的區(qū)間 $[l,r]$，如果剛好在某個塊區(qū)間內(nèi)，直接暴力修改 $[l,r]$ 的值；如果橫跨多個區(qū)間，先處理整塊，然后處理邊角料。

常用操作如下：

1. 區(qū)間加法、單點查詢

   最簡單的數(shù)列分塊操作，具體詳見代碼：

   #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. 區(qū)間加法、區(qū)間求和

   塊長同樣是 $\sqrt{n}$，由均值不等式可知此時單詞操作的時間復(fù)雜度最優(yōu)，為 $O(\sqrt{n})$。預(yù)處理每一個塊的區(qū)間和 $s$。

   對于區(qū)間 $[l,r]$ 的查詢操作，考慮幾種情況：

   • 若 $l$ 和 $r$ 在同一個塊內(nèi)，暴力統(tǒng)計，最壞時間復(fù)雜度為 $O(\sqrt{n})$；
   • 若 $l$ 和 $r$ 不在同一個塊內(nèi)，暴力統(tǒng)計不完整的塊，直接累加完整的塊的區(qū)間和，最壞時間復(fù)雜度為 $O(\sqrt{n})$。

   對于區(qū)間 $[l,r]$ 的加法操作，同樣按照上面的思考方式：

   • 若 $l$ 和 $r$ 在同一個塊內(nèi)，暴力修改區(qū)間即可，最壞時間復(fù)雜度為 $O(\sqrt{n})$；
   • 若 $l$ 和 $r$ 不在同一個塊內(nèi)，暴力修改不完整的塊同時更新 $s$，直接修改完整塊的 $s$，最壞時間復(fù)雜度為 $O(\sqrt{n})$。

   代碼如下：

   #include <bits/stdc++.h>
   using namespace std;
   #define int long longconst int maxn=50005;
   int a[maxn],id[maxn],tag[maxn]/*區(qū)間直接打標(biāo)記*/,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;
   }
   

塊狀數(shù)組