线段树
#include<cstdio> #include<algorithm> using namespace std; const int Nmax = 50005; int num[Nmax]; int n; struct Node { int l; int r; int data; }tree[Nmax*4]; void init() { for(int i=0;i<Nmax*4;i++) tree[i].l=tree[i].r=tree[i].data=0; } void push_up(int root) { tree[root].data=tree[root<<1].data+tree[root<<1|1].data; } void build(int root,int l,int r) { tree[root].l=l; tree[root].r=r; if(l==r) { tree[root].data=num[l]; return; } if(l<r) { int mid=(l+r)>>1; build(root*2,l,mid); build(root*2+1,mid+1,r); push_up(root); } } void update(int root,int l,int r,int data) { if(tree[root].l==l && tree[root].r == r) { tree[root].data+=data; return; } int mid=(tree[root].l+tree[root].r)>>1; if(mid<l) update(root<<1|1,l,r,data); else if(mid>=r) update(root<<1,l,r,data); else { update(root<<1,l,mid,data); update(root<<1|1,mid+1,r,data); } push_up(root); } int query(int root,int l,int r) { if(tree[root].l>=l && tree[root].r<=r) return tree[root].data; int mid=(tree[root].l+tree[root].r)>>1; int ans=0; if(mid<l) ans+=query(root<<1|1,l,r); else if(mid>=r) ans+=query(root<<1,l,r); else ans+=query(root<<1,l,mid)+query(root<<1|1,mid+1,r); return ans; } char s[10]; int main() { int t; //freopen("in.in","r",stdin); scanf("%d",&t); for(int k=1;k<=t;k++) { printf("Case %d: ",k); scanf("%d",&n); init(); for(int i=1;i<=n;i++) scanf("%d",&num[i]); build(1,1,n); /*int test=query(1,2,2); for(int i=1;i<=n;i++) for(int j=i;j<=n;j++) { printf("%d->%d:%d ",i,j,query(1,i,j)); } */ //printf("%d ",query(1,2,6)); /*for(int i=1;i<=26;i++) { if(tree[i].data) printf("num:%d , left:%d , right:%d , data:%d ",i,tree[i].l,tree[i].r,tree[i].data); }*/ while(1) { scanf("%s",s); if(s[0]=='E') break; int x,y; scanf("%d%d",&x,&y); if(s[0]=='A') { update(1,x,x,y); } else if(s[0]=='S') { update(1,x,x,-y); } else { printf("%d ",query(1,x,y)); } } } return 0; }