hdu 1166 线段树 单点修改 + 询问区间求和

#include <iostream>
#include <algorithm>
#include <stdlib.h>
#include <stdio.h>
#include <stack>
#include <string>
#include <string.h>
#include<cstring>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#include <set>
#include <math.h>
#include <cmath>
#include <map>
#include <queue>
using namespace std ;
typedef long long LL ;

// 线段树 单点修改，区间求和
#define left(x) (x<<1)
#define right(x) ((x<<1) + 1)
const int maxn=50005;
// 此线段树需要维护的附加信息是num，指的是每个节点所代表区间【l，r】之和
struct tree{
    int l,r,num;
};

tree anode[maxn<<2]; // 线段树的节点估计为2*maxn 个
int  data[maxn];
// 附加信息的向上更新只与该节点或者节点的子节点有关，故可以扩展线段树
void pushup(int n){
    anode[n].num=anode[left(n)].num + anode[right(n)].num;
    return ;
}// 向上更新
// 建线段树，从根节点1开始,调用为 build(1,n,1)
void build(int l, int r, int n){
    int mid;
    mid=(l+r)>>1;
    if(l==r){
        anode[n].l=l;
        anode[n].r=r;
        anode[n].num=data[l];
        return ;
    }
    anode[n].l=l;
    anode[n].r=r;
    build(l, mid, left(n));
    build(mid+1, r, right(n));
    pushup(n);// 先递归，后从下往上更新区间和值
}
// 线段树更新,从根节点开始, 调用为 update(aim_id, new_num, 1)
void update(int aim_id, int new_num, int n){
    if(anode[n].l == aim_id && anode[n].r== aim_id ){
        anode[n].num += new_num;
        return ;
    }
    if(anode[ left(n) ].l <= aim_id && anode[left(n)].r >=aim_id)
        update(aim_id, new_num, left(n));
    else update(aim_id, new_num, right(n));
    pushup(n);// 先递归需要更改的节点，然后从下往上的更新区间和值
    return ;
}
// 线段树查询,从根节点开始, 调用为 query(l,r, 1)
int query(int l, int r, int n){
    if(anode[n].l ==l && anode[n].r ==r)
        return anode[n].num;
    int mid;
    mid= (anode[n].l + anode[n].r)>>1;
    if(mid >=r) return query(l,r,left(n));
    else if(mid< l) return query(l,r,right(n));
    else return query(l,mid,left(n)) + query(mid+1, r, right(n));
}

int  main(){
    int ca,k=1;
    scanf("%d",&ca);
    while(ca--){
            int n;
        scanf("%d",&n);
    for(int i=1 ; i<=n; i++)
        scanf("%d",&data[i]);
    build(1,n,1);
    printf("Case %d:\n",k++);
    char od[12];
    while(1){
        scanf("%s",od);
        if(od[0] == ‘E‘) break;
        int a,b;
        scanf("%d%d",&a,&b);
        if(od[0] == ‘A‘)
            update(a,b,1);
        else if(od[0] == ‘S‘)
            update(a,-b,1);
        else
            printf("%d\n",query(a,b,1));
    }
    }
     return 0 ;
}