hdu1166(线段树单点更新&区间求和模板)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1166

题意：中文题诶～

思路：线段树单点更新，区间求和模板

代码：

 #include <iostream>

 #include <stdio.h>

 #define lson l, mid, rt << 1

 #define rson mid + 1, r, rt << 1 | 1

 using namespace std;

 const int MAXN = 5e4 + ;

 int sum[MAXN << ];

 void push_up(int rt){//向上求和

     sum[rt] = sum[rt << ] + sum[rt <<  | ];

 }

 //建树

 void build(int l, int r, int rt){//sum[rt] 对应区间 [l, r] 的和

     if(l == r){

         scanf("%d", &sum[rt]);

         return;

     }

     int mid = (l + r) >> ;

     build(lson);

     build(rson);

     push_up(rt);//向上更新节点

 }

 //单点更新

 void updata(int p, int add, int l, int r, int rt){//在p点增加add

     if(l == r){//找到p点

         sum[rt] += add;//单点更新

         return;

     }

     int mid = (l + r) >> ;

     if(p <= mid) updata(p, add, lson);

     else updata(p, add, rson);

     push_up(rt);//向上更新节点

 }

 //区间求和

 int query(int L, int R, int l, int r, int rt){//对[L, R]区间求和

     if(L <= l && R >= r) return sum[rt];//当前区间[l, r]包含在求和区间[L, R]中

     int ans = ;

     int mid = (l + r) >> ;

     if(L <= mid) ans += query(L, R, lson);//L在mid左边

     if(R > mid) ans += query(L, R, rson);//R在mid右边

     return ans;

 }

 int main(void){

     int t, n;

     scanf("%d", &t);

     for(int i = ; i <= t; i++){

         printf("Case %d:\n", i);

         scanf("%d", &n);

         build(, n, );

         char s[];

         while(scanf("%s", s) && s[] != 'E'){

             int x, y;

             scanf("%d%d", &x, &y);

             if(s[] == 'Q') printf("%d\n", query(x, y, , n, ));

             else if(s[] == 'A') updata(x, y, , n, );

             else updata(x, -y, , n, );

         }

     }

     return ;

 }