题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=1166php
一个线段树区间求和的模板题了。ios
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 6 #define MID(l,r) (l+r)>>1 7 #define lson root<<1 8 #define rson root<<1|1 9 10 const int maxn=5e4+5; 11 struct Tree 12 { 13 int l,r; 14 int sum; 15 }tree[maxn*3]; 16 17 int arr[maxn],ans; 18 19 void Build(int root,int l,int r) 20 { 21 tree[root].l=l; 22 tree[root].r=r; 23 if(l==r) 24 tree[root].sum=arr[l]; 25 else 26 { 27 int mid=MID(l,r); 28 Build(lson,l,mid); 29 Build(rson,mid+1,r); 30 tree[root].sum=tree[lson].sum+tree[rson].sum; 31 } 32 } 33 34 void Query(int root,int x,int y) 35 { 36 if(x<=tree[root].l&&y>=tree[root].r) 37 ans+=tree[root].sum; 38 else 39 { 40 int mid=MID(tree[root].l,tree[root].r); 41 if(x>mid) 42 { 43 Query(rson,x,y); 44 } 45 else if(y<=mid) 46 { 47 Query(lson,x,y); 48 } 49 else 50 { 51 Query(lson,x,y); 52 Query(rson,x,y); 53 } 54 } 55 } 56 57 void Update(int root,int x,int y) 58 { 59 tree[root].sum+=y; 60 if(tree[root].l==x&&tree[root].r==x) 61 return ; 62 int mid=MID(tree[root].l,tree[root].r); 63 if(x>mid) 64 Update(rson,x,y); 65 else 66 Update(lson,x,y); 67 68 } 69 70 int main() 71 { 72 int T; 73 cin>>T; 74 for(int flag=1;flag<=T;flag++) 75 { 76 int n; 77 cin>>n; 78 for(int i=1;i<=n;i++) 79 scanf("%d",&arr[i]); 80 Build(1,1,n); 81 printf("Case %d:\n",flag); 82 char s[10]; 83 while(scanf("%s",s)!=EOF) 84 { 85 if(strcmp(s,"End")==0) 86 break; 87 else if(strcmp(s,"Add")==0) 88 { 89 int x,y; 90 scanf("%d%d",&x,&y); 91 Update(1,x,y); 92 } 93 else if(strcmp(s,"Sub")==0) 94 { 95 int x,y; 96 scanf("%d%d",&x,&y); 97 Update(1,x,-y); 98 } 99 else if(strcmp(s,"Query")==0) 100 { 101 int x,y; 102 scanf("%d%d",&x,&y); 103 ans=0; 104 Query(1,x,y); 105 printf("%d\n",ans); 106 } 107 } 108 } 109 return 0; 110 }