题目链接 :https://cn.vjudge.net/problem/HDU-1166

线段树的基本操作,单点更新,区间查询

 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std;
const int maxn = 1e6 + 5;
#define ll long long

struct node
{
    int val;
}e[maxn];
int a[maxn];
void pushup(int cur){
    e[cur].val = e[cur<<1].val + e[cur<<1|1].val;
}
void build(int l, int r, int cur) {
    if(l == r) {
        e[cur].val = a[l];
        return ;
    }
    int m = l + r >> 1;
    build(l, m, cur<<1);
    build(m + 1, r, cur<<1|1);
    pushup(cur);
}
void update(int cl, int cr, int cur, int flag, int pos, int val) {
    if(cl == cr) {
        e[cur].val += flag * val;
        return ;
    }
    int m = cl + cr >> 1;
    if(pos <= m) update(cl, m, cur<<1, flag, pos, val);
    else update(m + 1, cr, cur<<1|1, flag, pos, val);
    pushup(cur);
}
int query(int cl, int cr, int cur, int l, int r) {
    if(l <= cl && cr <= r)
        return e[cur].val;
    int ans = 0;
    int m = cl + cr >> 1;
    if(l <= m) ans += query(cl, m, cur<<1, l, r);
    if(m < r) ans += query(m + 1, cr, cur<<1|1, l, r);
    return ans;
}
int main()
{
    int T, t = 1, n, l, r;
    scanf("%d",&T);
    while(T--) {
        scanf("%d",&n);
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
        }
        build(1, n, 1);
        char s[10];
        printf("Case %d:\n",t++);
        while(~scanf("%s", s)) {
            if(s[0] == 'E')break;
            scanf("%d%d", &l, &r);
            if(s[0] == 'Q') {
                printf("%d\n", query(1, n, 1, l, r));
            }
            else if(s[0] == 'A'){
                update(1, n, 1, 1, l, r);
            }
            else {
                update(1, n, 1, -1, l, r);
            }
        }


    }
    return 0;
}