題目描述

　　有一個長度為\(n\)的數組\(A\)和\(n\)個區間\([l_i,r_i]\)，有\(q\)次操作：

　　　\(1~x~y\)：把\(a_x\)改成\(y\)

　　　\(2~x~y\)：求第\(l\)個區間到第\(r\)個區間的區間和的和。

　　\(n,q\leq {10}^5,a_i\leq {10}^9\)

題解

　　分塊。

　　設\(s_i\)為第\(i\)塊的所有區間的區間和，\(d_{i,j}\)為第\(i\)塊有多少個區間包含了\(j\)這個位置。

　　修改時修改樹狀數組和每個區間的區間和。設當前\(a_x=v\)，則\(s_i+=(y-v)\times d_{i,x}\)

　　查詢時完整的區間直接查詢區間和，不完整的區間就暴力查詢。

　　設塊大小為\(m\)，時間復雜度為
\[ T(n)=O(\frac{n}{m}+m\log n) \]
　　當\(m=\sqrt{\frac{n}{\log n}}\)時
\[ T(n)_{\min}=O(n\sqrt{n\log n}) \]

代碼

#include<cstdio> #include<cstring> #include<algorithm> #include<cstdlib> #include<ctime> #include<utility> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pii; ull c[100010]; int a[100010]; int n; void add(int x,ull v) {for(;x<=n;x+=x&-x)c[x]+=v; } ull sum(int x) {ull s=0;for(;x;x-=x&-x)s+=c[x];return s; } int bl; ull s[1010]; int d[1010][100010]; int l[100010]; int r[100010]; int block[100010]; int left[100010]; int right[100010]; int main() {memset(c,0,sizeof c); // freopen("xsy2111.in","r",stdin); // freopen("xsy2111.out","w",stdout);int m;scanf("%d",&n);int i;for(i=1;i<=n;i++){scanf("%d",&a[i]);add(i,a[i]);}bl=100;m=(n+bl-1)/bl;for(i=1;i<=n;i++)block[i]=(i+bl-1)/bl;for(i=1;i<=m;i++){left[i]=(i-1)*bl+1;right[i]=min(i*bl,n);}for(i=1;i<=n;i++){scanf("%d%d",&l[i],&r[i]);s[block[i]]+=sum(r[i])-sum(l[i]-1);d[block[i]][l[i]]++;if(r[i]<n)d[block[i]][r[i]+1]--;}int j;for(i=1;i<=m;i++)for(j=2;j<=n;j++)d[i][j]+=d[i][j-1];int q;scanf("%d",&q);int op,x,y,k;for(i=1;i<=q;i++){scanf("%d%d%d",&op,&x,&y);if(op==1){int v=a[x];for(j=1;j<=m;j++)s[j]+=ull(y-v)*d[j][x];add(x,y-v);a[x]=y;}else{ull ans=0;for(j=block[x];j<=block[y];j++)if(left[j]>=x&&right[j]<=y)ans+=s[j];else{int mi=max(left[j],x);int mx=min(right[j],y);for(k=mi;k<=mx;k++)ans+=sum(r[k])-sum(l[k]-1);}printf("%llu\n",ans);}}return 0; }

轉載于:https://www.cnblogs.com/ywwyww/p/8511326.html

總結

以上是生活随笔為你收集整理的【XSY2111】Chef and Churus 分块 树状数组的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。