題意：在序列中修改單點和查詢區間和

#include<iostream> #include<cstdio> #include<cstring> #define ls l,m,rt<<1 #define rs m+1,r,rt<<1|1 using namespace std; const int maxn=50005*4; int sum[maxn<<2],add[maxn<<2];//sum求和，add懶惰標記 int a[maxn]={0},n=50005;//存原數組數據下標[1,n] //更新節點信息，這里是求和 void pushup(int rt) {sum[rt]=sum[rt<<1]+sum[rt<<1|1]; } //建樹 void pushdown(int rt,int ln,int rn) {//ln,rn為左子樹，右子樹的數量if(add[rt])//下推標記 {add[rt<<1]+=add[rt];add[rt<<1|1]+=add[rt];sum[rt<<1]+=add[rt]*ln;sum[rt<<1|1]+=add[rt]*rn;add[rt]=0;//清除本節點標記 } } void build(int l,int r,int rt)//rt表示當前節點編號 {if(l==r){sum[rt]=a[l];return;}int m=(l+r)>>1;build(l,m,rt<<1);build(m+1,r,rt<<1|1);pushup(rt); }//點修改a[L]+=c; //比如update(a,-b,1,n,1);//修改a點的值，減去b，當前節點區間是1到n，起始點是1 void update(int L,int c,int l,int r,int rt) {//l,r當前節點區間，rt當前節點編號，L需要修改的節點，c修改的值if(l==r){sum[rt]+=c;return;}int m=(l+r)>>1;//根據條件判斷調用左子樹還是右子樹if(L<=m)update(L,c,l,m,rt<<1);elseupdate(L,c,m+1,r,rt<<1|1);pushup(rt);//子節點更新，所以本節點也需要更新 }//區間修改a[r,t]+=c ////比如query(a,b,1,n,1))查詢a b之間的和，當前節點區間是1到n，起始點是1 void update_(int L,int R,int c,int l,int r,int rt) {//L,R表示操作區間，l,r表示當前節點區間，rt表示當前節點編號if(L<=l&&r<=R)//遍歷的區間在操作區間內 {sum[rt]+=c*(r-l+1);add[rt]+=c;return;}int m=(l+r)>>1;pushdown(rt,m-l+1,r-m);if(L<=m)update_(L,R,c,l,m,rt<<1);if(R>m)update_(L,R,c,m+1,r,rt<<1|1);pushup(rt); } //區間查詢 a[l,r]的和 //下推標記函數int query(int L,int R,int l,int r,int rt) {if(L<=l&&r<=R){return sum[rt];}int m=(l+r)>>1;pushdown(rt,m-l+1,r-m);int ans=0;if(L<=m)ans+=query(L,R,l,m,rt<<1);if(R>m)ans+=query(L,R,m+1,r,rt<<1|1);return ans; }int main() {int t,cnt=1;scanf("%d",&t);while(t--){memset(a,0,sizeof(a));memset(sum,0,sizeof(sum));memset(add,0,sizeof(add));scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);build(1,n,1);printf("Case %d:\n",cnt++);char str[20];while(scanf("%s",str)&&str[0]!='E'){int a,b;scanf("%d%d",&a,&b);if(str[0]=='Q'){query(a,b,1,n,1);}if(str[0]=='S')update(a,-b,1,n,1);//修改a點的值，減去b，當前節點區間是1到n，起始點是1if(str[0]=='A')update(a,b,1,n,1);if(str[0]=='Q')printf("%d\n",query(a,b,1,n,1));//查詢a b之間的和，當前節點區間是1到n，起始點是1 }}return 0; }

?

轉載于:https://www.cnblogs.com/fudanxi/p/11172549.html

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的HDU1166 敌兵布阵 [线段树模板]的全部內容，希望文章能夠幫你解決所遇到的問題。

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