kuangbin_SegTree A (HDU 1166)

大牛们的文章里这句 题意:O(-1) 思路:O(-1) 深深地嘲讽了我........

不过单点更新 区间求和也算是基本操作了吧 (虽然我还是看了好久才理解)

跟之前学图论的时候感觉完全不一样啊orz

#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
#define INF 0x3f3f3f3f
#define lson l, m, root<<1
#define rson m+1, r, root<<1|1
using namespace std;

const int MAXN = 5e4+10;
int sum[MAXN*4];

void pushup(int root)
{
    sum[root] = sum[root<<1] + sum[root<<1|1];
}

void build(int l, int r, int root)
{
    if(l == r) scanf("%d", &sum[root]);
    else{
        int m = (l + r) >> 1;
        build(lson);
        build(rson);
        pushup(root);
    }
}

void update(int point, int val, int l, int r, int root)
{
    if(l == r) sum[root] += val;
    else{
        int m = (l + r) >> 1;
        if(point <= m) update(point, val, lson);
        else update(point, val, rson);
        pushup(root);
    }
}

int query(int L, int R, int l, int r, int root)
{
    if(L <= l && R >= r) return sum[root];
    int res = 0;
    int m = (l + r) >> 1;
    if(L <= m) res += query(L, R, lson);
    if(R > m) res += query(L, R, rson);
    return res;
}

int main()
{
    int t, n;
    scanf("%d", &t);
    for(int kase = 1; kase <= t; kase++){
        printf("Case %d:
", kase);
        scanf("%d", &n);
        build(1, n, 1);
        char op[10];
        while(scanf("%s", op), op[0] != 'E'){
            int u, v;
            scanf("%d%d", &u, &v);
            if(op[0] == 'A') update(u, v, 1, n, 1);
            else if(op[0] == 'S') update(u, -v, 1, n, 1);
            else printf("%d
", query(u, v, 1, n, 1));
        }
    }
    return 0;
}