C++ – HDU-1166 树状数组模板

题目链接

#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
using namespace std;
const int MAXN = 100001;
int n;
int tree[MAXN];
int a[MAXN];
int lowbit(int x) {
    return x & (-x);
}
void fadd(int pos, int val) {
    for(int i = pos; i <= n; i += lowbit(i))
        tree[i] += val;
}
void fsub(int pos, int val) {
    for(int i = pos; i <= n; i += lowbit(i))
        tree[i] -= val;
}
int fsum(int pos) {
    int ss = 0;
    for(int i = pos; i > 0; i -= lowbit(i))
        ss += tree[i];
    return ss;
}
int qu(int l, int r) {
    return fsum(r) - fsum(l - 1);
}
int main() {
    int t;
    scanf("%d", &t);
    for(int z = 1; z <= t; z++) {
        memset(tree, 0, sizeof tree);
        scanf("%d", &n);
        for(int i = 1; i <= n; i++){
            scanf("%d", &a[i]);
            fadd(i, a[i]);
        }
        printf("Case %d:\n", z);
        string x;
        while(cin >> x) {
            if(x == "End") break;
            int c1, c2;
            scanf("%d %d", &c1, &c2);
            if(x == "Add") fadd(c1, c2);
            else if(x == "Sub") fsub(c1, c2);
            else printf("%d\n", qu(c1, c2));
        }
    }
    return 0;
}