python/TangDou/AcWing/SegmentTree/ZKW/HDU1166.cpp

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

//快读
int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}

const int N = 50000 + 10;

int m = 1, n;
int d[N << 2];

//区间查询
int query(int l, int r) {
    int ans = 0;
    for (l = l + m - 1, r = r + m + 1; l ^ r ^ 1; l >>= 1, r >>= 1) {
        if (~l & 1) ans += d[l ^ 1]; // l是偶数
        if (r & 1) ans += d[r ^ 1];  // r是奇数
    }
    return ans;
}

//单点增加
void add(int x, int c) {
    d[m + x] += c;
    for (int i = (m + x) >> 1; i; i >>= 1) d[i] = d[i << 1] + d[i << 1 | 1];
}

void build(int n) {
    memset(d, 0, sizeof d);
    for (m = 1; m < n;) m <<= 1; // 强行开够（大于n）方便二进制访问叶节点
    for (int i = 1; i <= n; i++) d[m + i] = read();           //初始值
    for (int i = m; i; i--) d[i] = d[i << 1] + d[i << 1 | 1]; //待所有叶子节点有值后，统一执行一次向上数据统计信息汇总
}

int main() {
//文件输入输出
#ifndef ONLINE_JUDGE
    freopen("HDU1166.in", "r", stdin);
#endif
    int k = read();

    for (int q = 1; q <= k; q++) {
        n = read();
        //构建zkw线段树
        build(n);

        printf("Case %d:\n", q);

        char op[10];
        while (scanf("%s", op)) {
            if (op[0] == 'E') break;
            int l = read(), r = read();
            if (op[0] == 'Q')
                printf("%d\n", query(l, r));
            else if (op[0] == 'A')
                add(l, r);
            else if (op[0] == 'S')
                add(l, -r);
        }
    }
    return 0;
}