http://acm.hdu.edu.cn/showproblem.php?pid=1166
1 #include <bits/stdc++.h> 2 #define lid id<<1 3 #define rid id<<1|1 4 #define maxn 50005 5 using namespace std; 6 struct node 7 { 8 int l,r,num; 9 }tr[maxn*4]; 10 int s[maxn]; 11 12 void push_up(int id) 13 { 14 tr[id].num=tr[lid].num+tr[rid].num; 15 } 16 void build(int id,int l,int r) 17 { 18 tr[id].l=l;tr[id].r=r; 19 if(l==r) 20 { 21 tr[id].num=s[l]; 22 return ; 23 } 24 int mid=(l+r)>>1; 25 build(lid,l,mid); 26 build(rid,mid+1,r); 27 push_up(id); 28 } 29 void update(int id,int l,int r,int add) 30 { 31 if(tr[id].l==l&&tr[id].r==r) 32 { 33 tr[id].num+=add; 34 return ; 35 } 36 int mid=(tr[id].l+tr[id].r)>>1; 37 if(l<=mid) update(lid,l,r,add); 38 else update(rid,l,r,add); 39 push_up(id); 40 } 41 int query(int id,int l,int r) 42 { 43 if(tr[id].l>=l&&tr[id].r<=r) 44 { 45 return tr[id].num; 46 } 47 int mid=(tr[id].l+tr[id].r)>>1; 48 if(r<=mid) return query(lid,l,r); 49 else if(l>mid) return query(rid,l,r); 50 else return query(lid,l,mid)+query(rid,mid+1,r); 51 } 52 int main() 53 { 54 int t; 55 scanf("%d",&t); 56 int flag=0; 57 while(t--) 58 { 59 int n; 60 scanf("%d",&n); 61 for(int i=1;i<=n;i++) scanf("%d",&s[i]); 62 build(1,1,n); 63 char s[10]; 64 printf("Case %d: ",++flag); 65 while(~scanf("%s",s)) 66 { 67 int l,r,add; 68 if(s[0]=='E') break; 69 else if(s[0]=='A') 70 { 71 scanf("%d%d",&l,&add); 72 update(1,l,l,add); 73 } 74 else if(s[0]=='S') 75 { 76 scanf("%d%d",&l,&add); 77 update(1,l,l,-add); 78 } 79 else 80 { 81 scanf("%d%d",&l,&r); 82 int ans=query(1,l,r); 83 printf("%d ",ans); 84 } 85 } 86 } 87 return 0; 88 }