【線分樹】線分樹テンプレート胡浩版

#include 
#include 
#include 
#include 
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
const int N = 50010;
int tree[N<<2];

void push_up(int rt) 
{
    tree[rt] = tree[rt<<1] + tree[rt<<1|1];
}

void build(int l, int r, int rt) 
{
    if(l == r) {
        scanf("%d", &tree[rt]);
        return ;
    }
    int m = (l+r) >> 1;
    build(lson); build(rson);
    push_up(rt);
}

int query(int L, int R, int l, int r, int rt) 
{
    if(L <= l && r <= R) return tree[rt];
    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;
}

void update(int p, int val, int l, int r, int rt)
{
    if(l == r) {
        tree[rt] += val;
        return ;
    }
    int m = (l+r) >> 1;
    if(p <= m) update(p, val, lson);
    else update(p, val, rson);
    push_up(rt);
}

int main() 
{
    int T;
    scanf("%d", &T);
    while(T--) {
        int n;
        scanf("%d", &n);
        build(1, n, 1);
        char op[10];
        int a, b;
        while(~scanf("%s", op)) {
            scanf("%d%d", &a, &b);
            if(op[0] == 'Q') {
                int ans = query(a, b, 1, n, 1);
                printf("%d
", ans);
            }
            if(op[0] == 'A') update(a, b, 1, n, 1);
        }
    }
    return 0;
}