啥也不说了,直接贴代码,之前因为马虎写错了一个地方,就一直错误~_~
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 const int maxn=50005; 7 int tree[maxn<<2]; 8 void push_up(int rt) 9 { 10 tree[rt]=tree[rt<<1]+tree[rt<<1 | 1]; 11 } 12 void build(int rt,int first,int end) 13 { 14 if(first==end) 15 { 16 scanf("%d",&tree[rt]); 17 return ; 18 } 19 int mid=(first+end)>>1; 20 build(rt<<1,first,mid); 21 build(rt<<1 | 1,mid+1,end); 22 push_up(rt); 23 } 24 void Add(int rt,int first,int end,int a,int b) 25 { 26 if(first==end) 27 { 28 tree[rt]+=b; 29 return ; 30 } 31 int mid=(first+end)>>1; 32 if(a<=mid) 33 Add(rt<<1,first,mid,a,b); 34 if(a>mid) 35 Add(rt<<1 | 1,mid+1,end,a,b); 36 push_up(rt); 37 } 38 int Quary(int rt,int first,int end,int a,int b) 39 { 40 if(a<=first&&b>=end) 41 { 42 return tree[rt]; 43 } 44 int mid=(first+end)>>1; 45 int ans=0; 46 if(a<=mid) 47 ans+=Quary(rt<<1,first,mid,a,b); 48 if(b>mid) 49 ans+=Quary(rt<<1 | 1,mid+1,end,a,b); 50 return ans; 51 } 52 int main() 53 { 54 int t,n,k=0; 55 char s[10]; 56 int a,b; 57 cin>>t; 58 while(t--) 59 { 60 bool flag=false; 61 cin>>n; 62 build(1,1,n); 63 while(scanf("%s",s)&&s[0]!=‘E‘) 64 { 65 scanf("%d %d",&a,&b); 66 if(s[0]==‘Q‘) 67 { 68 if(!flag) 69 { 70 printf("Case %d:\n",++k); 71 flag=true; 72 } 73 printf("%d\n",Quary(1,1,n,a,b)); 74 } 75 if(s[0]==‘A‘) 76 Add(1,1,n,a,b); 77 if(s[0]==‘S‘) 78 Add(1,1,n,a,-b); 79 } 80 } 81 return 0; 82 }
原文:http://www.cnblogs.com/cxbky/p/4883482.html