摘要：
敌兵布阵 A国沿海岸线设立了N个工程营地。德里克和蒂迪的任务是监控这些工程营地的活动。然而，营地中敌军士兵的数量经常变化，德里克每次的询问都不同，因此蒂迪不得不一次数一个营地，很快就精疲力尽了。德里克对蒂迪的计算速度越来越不满：“你太胖了，你太慢了，我要解雇你！”但风衣挂断了电话。然而，如果你的程序不够高效，Tidy仍然会被Derek责骂。输入的第一行中的整数T表示有T组数据。
Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 18120Accepted Submission(s): 7877
Problem Description
C国的死对头A国这段时间正在进行军事演习，所以C国间谍头子Derek和他手下Tidy又开始忙乎了。A国在海岸线沿直线布置了N个工兵营地,Derek和Tidy的任务就是要监视这些工兵营地的活动情况。由于采取了某种先进的监测手段，所以每个工兵营地的人数C国都掌握的一清二楚,每个工兵营地的人数都有可能发生变动，可能增加或减少若干人手,但这些都逃不过C国的监视。
中央情报局要研究敌人究竟演习什么战术,所以Tidy要随时向Derek汇报某一段连续的工兵营地一共有多少人,例如Derek问:“Tidy,马上汇报第3个营地到第10个营地共有多少人!”Tidy就要马上开始计算这一段的总人数并汇报。但敌兵营地的人数经常变动，而Derek每次询问的段都不一样，所以Tidy不得不每次都一个一个营地的去数，很快就精疲力尽了，Derek对Tidy的计算速度越来越不满:"你个死肥仔，算得这么慢，我炒你鱿鱼!”Tidy想：“你自己来算算看，这可真是一项累人的工作!我恨不得你炒我鱿鱼呢!”无奈之下，Tidy只好打电话向计算机专家Windbreaker求救,Windbreaker说：“死肥仔，叫你平时做多点acm题和看多点算法书，现在尝到苦果了吧!”Tidy说："我知错了。。。"但Windbreaker已经挂掉电话了。Tidy很苦恼，这么算他真的会崩溃的，聪明的读者，你能写个程序帮他完成这项工作吗？不过如果你的程序效率不够高的话，Tidy还是会受到Derek的责骂的.
中央情报局要研究敌人究竟演习什么战术,所以Tidy要随时向Derek汇报某一段连续的工兵营地一共有多少人,例如Derek问:“Tidy,马上汇报第3个营地到第10个营地共有多少人!”Tidy就要马上开始计算这一段的总人数并汇报。但敌兵营地的人数经常变动，而Derek每次询问的段都不一样，所以Tidy不得不每次都一个一个营地的去数，很快就精疲力尽了，Derek对Tidy的计算速度越来越不满:"你个死肥仔，算得这么慢，我炒你鱿鱼!”Tidy想：“你自己来算算看，这可真是一项累人的工作!我恨不得你炒我鱿鱼呢!”无奈之下，Tidy只好打电话向计算机专家Windbreaker求救,Windbreaker说：“死肥仔，叫你平时做多点acm题和看多点算法书，现在尝到苦果了吧!”Tidy说："我知错了。。。"但Windbreaker已经挂掉电话了。Tidy很苦恼，这么算他真的会崩溃的，聪明的读者，你能写个程序帮他完成这项工作吗？不过如果你的程序效率不够高的话，Tidy还是会受到Derek的责骂的.
Input
第一行一个整数T，表示有T组数据。
每组数据第一行一个正整数N（N<=50000）,表示敌人有N个工兵营地，接下来有N个正整数,第i个正整数ai代表第i个工兵营地里开始时有ai个人（1<=ai<=50）。
接下来每行有一条命令，命令有4种形式：
(1) Add i j,i和j为正整数,表示第i个营地增加j个人（j不超过30）
(2)Sub i j ,i和j为正整数,表示第i个营地减少j个人（j不超过30）;
(3)Query i j ,i和j为正整数,i<=j，表示询问第i到第j个营地的总人数;
(4)End 表示结束，这条命令在每组数据最后出现;
每组数据最多有40000条命令
每组数据第一行一个正整数N（N<=50000）,表示敌人有N个工兵营地，接下来有N个正整数,第i个正整数ai代表第i个工兵营地里开始时有ai个人（1<=ai<=50）。
接下来每行有一条命令，命令有4种形式：
(1) Add i j,i和j为正整数,表示第i个营地增加j个人（j不超过30）
(2)Sub i j ,i和j为正整数,表示第i个营地减少j个人（j不超过30）;
(3)Query i j ,i和j为正整数,i<=j，表示询问第i到第j个营地的总人数;
(4)End 表示结束，这条命令在每组数据最后出现;
每组数据最多有40000条命令
Output
对第i组数据,首先输出“Case i:”和回车,
对于每个Query询问，输出一个整数并回车,表示询问的段中的总人数,这个数保持在int以内。
对于每个Query询问，输出一个整数并回车,表示询问的段中的总人数,这个数保持在int以内。
Sample Input
1 10 1 2 3 4 5 6 7 8 9 10 Query 1 3 Add 3 6 Query 2 7 Sub 10 2 Add 6 3 Query 3 10 End
Sample Output
Case 1: 6 33 59
1 /*功能Function Description: HDOJ-1166 树状数组插点问线 、线段树解法 2 开发环境Environment: DEV C++ 4.9.9.1 3 技术特点Technique: 4 版本Version: 5 作者Author: 可笑痴狂 6 日期Date: 20120808 7 备注Notes: 8 */ 9 10 /* 11 //代码一：----树状数组 12 #include<stdio.h> 13 #include<string.h> 14 15 int n; 16 int a[50005]; 17 18 int lowbit(int i) 19 { 20 return i&(-i); 21 } 22 23 void update(int i,int num) 24 { 25 while(i<=n) 26 { 27 a[i]+=num; 28 i+=lowbit(i); 29 } 30 } 31 32 int getsum(int i) 33 { 34 int sum=0; 35 while(i>0) 36 { 37 sum+=a[i]; 38 i-=lowbit(i); 39 } 40 return sum; 41 } 42 43 int main() 44 { 45 int T,i,j,m; 46 char cmd[10]; 47 scanf("%d",&T); 48 for(m=1;m<=T;++m) 49 { 50 printf("Case %d:\n",m); 51 memset(a,0,sizeof(a)); 52 scanf("%d",&n); 53 for(i=1;i<=n;++i) 54 { 55 scanf("%d",&j); 56 update(i,j); 57 } 58 while(scanf("%s",cmd)) 59 { 60 if(cmd[0]=='A') 61 { 62 scanf("%d%d",&i,&j); 63 update(i,j); 64 } 65 else if(cmd[0]=='Q') 66 { 67 scanf("%d%d",&i,&j); 68 printf("%d\n",getsum(j)-getsum(i-1)); 69 } 70 else if(cmd[0]=='S') 71 { 72 scanf("%d%d",&i,&j); 73 update(i,-j); 74 } 75 else 76 break; 77 } 78 } 79 return 0; 80 } 81 */ 82 83 //代码二：-------线段树 84 85 #include<stdio.h> 86 #define MAX 50000 87 88 structnode 89 { 90 intlc,rc; 91 int sum; //存放的是从lc到rc之间的总人数 92 }tree[MAX*3]; 93 94 void build(int s,int t,intT) 95 { 96 int mid=(s+t)>>1; 97 tree[T].lc=s; 98 tree[T].rc=t; 99 tree[T].sum=0; 100 if(s==t) 101 return; 102 build(s,mid,T<<1); 103 build(mid+1,t,(T<<1)|1); 104 } 105 106 void insert(int num,int add,int T) //编号为num的线段增加了add，从T开始查找，在含有num的线段中sum都加add 107 { 108 if(num<tree[T].lc||num>tree[T].rc) 109 return; 110 else 111 { 112 tree[T].sum+=add; 113 if(tree[T].lc==tree[T].rc) 114 return; 115 if(num<=((tree[T].lc+tree[T].rc)>>1)) 116 insert(num,add,T<<1); 117 else 118 insert(num,add,(T<<1)|1); 119 } 120 } 121 122 int getsum(int s,int t,int T) //统计从s到t的总人数，从T开始查找知道找到该条线段为止 123 { 124 int mid=(tree[T].lc+tree[T].rc)>>1; 125 if(tree[T].lc==s&&tree[T].rc==t) 126 returntree[T].sum; 127 if(t<=mid) 128 return getsum(s,t,T<<1); 129 else if(s>mid) 130 return getsum(s,t,(T<<1)|1); 131 else 132 return getsum(s,mid,T<<1)+getsum(mid+1,t,(T<<1)|1); 133 } 134 135 136 intmain() 137 { 138 intk,i,j,m,n,t; 139 char cmd[10]; 140 scanf("%d",&k); 141 for(m=1;m<=k;++m) 142 { 143 printf("Case %d:\n",m); 144 scanf("%d",&n); 145 build(1,n,1); 146 for(i=1;i<=n;++i) 147 { 148 scanf("%d",&t); 149 insert(i,t,1); 150 } 151 while(scanf("%s",cmd)) 152 { 153 if(cmd[0]=='A') 154 { 155 scanf("%d%d",&i,&j); 156 insert(i,j,1); 157 } 158 else if(cmd[0]=='Q') 159 { 160 scanf("%d%d",&i,&j); 161 printf("%d\n",getsum(i,j,1)); 162 } 163 else if(cmd[0]=='S') 164 { 165 scanf("%d%d",&i,&j); 166 insert(i,-j,1); 167 } 168 else 169 break; 170 } 171 } 172 return 0; 173 }