hdu 1166
模板：
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int maxn = 50005; int sum[maxn<<2]; void Pushdown(int rt){ sum[rt] = sum[rt<<1]+sum[rt<<1|1]; } void Build(int rt,int l,int r){ //建树 if(l==r){ scanf("%d",&sum[rt]); return ; } int mid = (l+r)>>1; Build(rt<<1,l,mid); Build(rt<<1|1,mid+1,r); Pushdown(rt); } void Update(int pos,int x,int rt,int l,int r){ //单点修改 if(l==r){ sum[rt]+=x; return ; } int mid = (l+r)>>1; if(pos<=mid) Update(pos,x,rt<<1,l,mid); else Update(pos,x,rt<<1|1,mid+1,r); Pushdown(rt); } int Query(int L,int R,int rt,int l,int r){ //区间查询 if(L<=l&&r<=R){ return sum[rt]; } int mid = (l+r)>>1,ans = 0; if(L<=mid) ans += Query(L,R,rt<<1,l,mid); if(R>mid) ans += Query(L,R,rt<<1|1,mid+1,r); return ans; } int main(void) { int T,pt = 1;scanf("%d",&T); while(T--){ memset(sum,0,sizeof(sum)); int n;scanf("%d",&n); Build(1,1,n); printf("Case %d:\n",pt++); for(;;){ char ss[10];scanf("%s",ss); if(strcmp(ss,"End")==0) break; int x,y;scanf("%d%d",&x,&y); if(ss[0]=='Q') printf("%d\n",Query(x,y,1,1,n)); else if(ss[0]=='S') Update(x,-y,1,1,n); else Update(x,y,1,1,n); } } return 0; }
