学步园

入门线段树题

线段树写法，不过还是树状数组比较好写

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int const MAXN = 50010;
#define Lson l,m,rt<<1
#define Rson m+1,r,rt<<1|1
struct Tree{
    int l,r;
    int v;
}tree[MAXN<<2];
inline void PushPlus(int rt){
    tree[rt].v = tree[rt<<1].v + tree[rt<<1|1].v;
}
void Build(int l,int r,int rt){
    tree[rt].l = l;
    tree[rt].r = r;
    if(l == r){
        scanf("%d",&tree[rt].v);
        return ;
    }
    int m = (l + r)>>1;
    Build(Lson);
    Build(Rson);
    PushPlus(rt);
    //cout<<rt<<" "<<tree[rt].v<<endl;
}
void Update(int p,int s,int l,int r,int rt){
    if(l == r){
        tree[rt].v += s;
        return ;
    }
    int m = (l + r)>>1;
    if(p <= m) Update(p,s,Lson);
    else Update(p,s,Rson);
    PushPlus(rt);
}
int Query(int L,int R,int l,int r,int rt){
    if(l > R || r < L) return -1;
    if(L <= l && r <= R){
        //cout<<L<<" "<<R<<endl;
        return tree[rt].v;
    }
    int m = (l + r) >> 1;
    int ret = 0;
    if(L <= m) ret += Query(L,R,Lson);
    if(R > m) ret += Query(L,R,Rson);
    return ret;
}
int main(){
    int t;
    while(~scanf("%d",&t)){
        for(int k = 1;k <= t;k++){
            int n;
            scanf("%d",&n);
            Build(1,n,1);
            printf("Case %d:\n",k);
            while(1){
                char str[10];
                int a,b;
                scanf("%s",str);
                if(str[0] == 'E') break;
                scanf("%d%d",&a,&b);
                if(str[0] == 'Q') printf("%d\n",Query(a,b,1,n,1));
                else{
                    if(str[0] == 'S') b = -b;
                    Update(a,b,1,n,1);
                }
            }
        }
    }
    return 0;
}