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 # include <iostream> 2 # include <cstdio> 3 # include <cstring> 4 # include <algorithm> 5 # include <cmath> 6 # include <queue> 7 # define LL long long 8 using namespace std ; 9 10 const int maxn = 50010; 11 12 int sum[maxn<<2] ; //结点开4倍 13 14 void PushUP(int rt) //更新到父节点 15 { 16 sum[rt] = sum[rt * 2] + sum[rt * 2 + 1] ; //rt 为当前结点 17 } 18 19 void build(int l , int r , int rt) //构建线段树 20 { 21 if (l == r) 22 { 23 scanf("%d" , &sum[rt]) ; 24 return ; 25 } 26 int m = (l + r) / 2 ; 27 build(l , m , rt * 2) ; 28 build(m + 1 , r , rt * 2 +1) ; 29 PushUP(rt) ; 30 } 31 32 void updata(int p , int add , int l , int r , int rt) //单点增减 33 { 34 if (l == r) 35 { 36 sum[rt] += add ; 37 return ; 38 } 39 int m = (l + r) / 2 ; 40 if (p <= m) 41 updata(p , add , l , m , rt * 2) ; 42 else 43 updata(p , add , m + 1 , r , rt * 2 + 1) ; 44 PushUP(rt) ; 45 } 46 47 int query(int L , int R , int l , int r , int rt) //区间求和 48 { 49 if (L <= l && r <= R) 50 return sum[rt] ; 51 int m = (l + r) / 2 ; 52 int ret = 0 ; 53 if (L <= m) 54 ret += query(L , R , l , m , rt * 2) ; 55 if (R > m) 56 ret += query(L , R , m + 1 , r , rt * 2 + 1) ; 57 return ret ; 58 } 59 60 int main () 61 { 62 //freopen("in.txt","r",stdin) ; 63 int T , n; 64 int Case = 0 ; 65 scanf("%d" , &T) ; 66 while (T--) 67 { 68 scanf("%d" , &n) ; 69 build(1 , n , 1) ; 70 char op[10] ; 71 Case++ ; 72 printf("Case %d: " , Case) ; 73 while (scanf("%s" , op)) 74 { 75 if (op[0] == 'E') //结束 76 break ; 77 int a , b ; 78 scanf("%d %d" , &a , &b) ; 79 if (op[0] == 'Q') //求a,b区间的和 80 printf("%d ", query(a , b , 1 , n , 1)) ; 81 else if (op[0] == 'S') //将第a个地方减少b 82 updata(a , -b , 1 , n , 1) ; 83 else if (op[0] == 'A') //将第a个地方增加b 84 updata(a , b , 1 , n , 1) ; 85 } 86 } 87 88 89 return 0 ; 90 }