正題

題目鏈接：我是鏈接
其實洛谷線段樹模板也是一樣的：三種方法AC評測鏈接

---

題目大意

要求支持區(qū)間修改，區(qū)間求和。

---

線段樹

直接用一個lazy標記，在之前的博客里有說

---

code1

#include<cstdio> #include<algorithm> #define N 100010 #define ll long long using namespace std; struct treenode{int l,r;ll val,lazy; }t[N*4]; int n,m,l,r; ll x; char c[2]; void build(int x,int l,int r)//建樹 {t[x].l=l;t[x].r=r;if(l==r){scanf("%lld",&t[x].val);return;}int mid=(l+r)>>1;build(x*2,l,mid);build(x*2+1,mid+1,r);t[x].val=t[x*2].val+t[x*2+1].val; } void downdata(int x)//下傳標記 {if(t[x].lazy){t[x*2].lazy+=t[x].lazy;t[x*2].val+=t[x].lazy*(t[x*2].r-t[x*2].l+1);t[x*2+1].lazy+=t[x].lazy;t[x*2+1].val+=t[x].lazy*(t[x*2+1].r-t[x*2+1].l+1);t[x].lazy=0;} } void change(int x,int l,int r,ll num)//區(qū)間修改 {if(t[x].l==l&&t[x].r==r){t[x].val+=num*(t[x].r-t[x].l+1);t[x].lazy+=num;return;}downdata(x);int mid=(t[x].l+t[x].r)>>1;if(r<=mid) change(x*2,l,r,num);else if(l>mid) change(x*2+1,l,r,num);else change(x*2,l,mid,num),change(x*2+1,mid+1,r,num);t[x].val=t[x*2].val+t[x*2+1].val; } ll find(int x,int l,int r)//區(qū)間查詢 {if(t[x].l==l&&t[x].r==r)return t[x].val;downdata(x);int mid=(t[x].l+t[x].r)>>1;if(r<=mid) return find(x*2,l,r);else if(l>mid) return find(x*2+1,l,r);else return find(x*2,l,mid)+find(x*2+1,mid+1,r); } int main() {scanf("%d%d",&n,&m);build(1,1,n);for(int i=1;i<=m;i++){scanf("%s %d %d",c,&l,&r);if(c[0]=='Q') printf("%lld\n",find(1,l,r));else{scanf("%lld",&x);change(1,l,r,x);}} }

---

樹狀數(shù)組

我們可以用樹狀數(shù)組維護一個查分數(shù)組bb和一個bi×ibi×i的前綴和，然后再記錄原來的a數(shù)組的前綴和sumsum，對于改寫我們就將兩個數(shù)組改變，然后查詢就

(sumr+(r+1)?ask(c0,r)?ask(c1,r))?(suml?1+l?ask(c1,l?1)?ask(c1,l?1)(sumr+(r+1)?ask(c0,r)?ask(c1,r))?(suml?1+l?ask(c1,l?1)?ask(c1,l?1)

---

code2

#include<cstdio> #include<algorithm> #include<iostream> #define lobit(x) x&-x using namespace std; long long t[2][100010],x,a[100010],sum[100010]; int n,m,l,r; void add(int k,int x,int num)//修改 {while(x<=n){t[k][x]+=num;x+=lobit(x);} } long long ask(int k,int x)//查詢 {long long sum=0;while(x>0){sum+=t[k][x];x-=lobit(x);}return sum; } int main() {scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%lld",&a[i]);sum[i]=sum[i-1]+a[i];}for(int i=1;i<=m;i++){char c[2];scanf("%s %d %d",c,&l,&r);if(c[0]=='Q'){long long ans=sum[r]+(r+1)*ask(0,r)-ask(1,r);ans-=sum[l-1]+l*ask(0,l-1)-ask(1,l-1);//查詢printf("%lld\n",ans);}else{scanf("%d",&x);add(0,l,x);add(0,r+1,-x);add(1,l,l*x);add(1,r+1,-(r+1)*x);//修改}} }

---

分塊

將整段分成多塊，然后修改如果到達一塊就直接修改像線段樹一樣標記，如果不到達一塊就暴力修改。
就是：
“大段維護，局部樸素”——算法競賽

---

code3

#include<cstdio> #include<algorithm> #include<cmath> #define ll long long #define N 100010 using namespace std; ll a[N],sum[N],add[N]; int L[N],R[N],d; int pos[N]; int n,m,t,l,r; char op[3]; void change(int l,int r,long long d) {int p=pos[l],q=pos[r];if(p==q){for(int i=l;i<=r;i++) a[i]+=d;sum[p]+=d*(r-l+1);}//全都在一塊中else{for(int i=p+1;i<=q-1;i++) add[i]+=d;//維護中間段落for(int i=l;i<=R[p];i++) a[i]+=d;sum[p]+=d*(R[p]-l+1);for(int i=L[q];i<=r;i++) a[i]+=d;sum[q]+=d*(r-L[q]+1);//暴力局部修改} } ll ask(int l,int r) {int p=pos[l],q=pos[r];ll ans=0;if(p==q){for(int i=l;i<=r;i++) ans+=a[i];ans+=add[p]*(r-l+1);}//全部都在一塊中else{for(int i=p+1;i<=q-1;i++)ans+=sum[i]+add[i]*(R[i]-L[i]+1);//累加中間段落for(int i=l;i<=R[p];i++) ans+=a[i];ans+=add[p]*(R[p]-l+1);for(int i=L[q];i<=r;i++) ans+=a[i];ans+=add[q]*(r-L[q]+1);//暴力局部累加}return ans; } int main() {scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%lld",&a[i]);t=sqrt(n);for(int i=1;i<=t;i++){L[i]=(i-1)*t+1;R[i]=i*t;}//標記每塊左右if(R[t]<n) t++,L[t]=R[t-1]+1,R[t]=n;//補足尾部for(int i=1;i<=t;i++)for(int j=L[i];j<=R[i];j++){pos[j]=i;//表示屬于哪個塊sum[i]+=a[j];//計算段落和}for(int i=1;i<=m;i++){scanf("%s %d %d",op,&l,&r);if(op[0]=='C'){scanf("%d",&d);change(l,r,d);}else printf("%lld\n",ask(l,r));} }

總結(jié)

以上是生活随笔為你收集整理的POJ3468-A Simple Problem with Integers【线段树,树状数组,分块】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。