python/TangDou/AcWing/BIT/242.cpp

#include <bits/stdc++.h>

using namespace std;
const int N = 100010;

int n, m;
int a[N];
// 树状数组模板
typedef long long LL;
#define lowbit(x) (x & -x)
int c[N];
void add(int x, int d) {
    for (int i = x; i < N; i += lowbit(i)) c[i] += d;
}
LL sum(int x) {
    LL res = 0;
    for (int i = x; i; i -= lowbit(i)) res += c[i];
    return res;
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

    // 方法1：也可以这么做，但是方法比较笨拙
    // 树状数组初始化，保存差分值
    // for (int i = 1; i <= n; i++) add(i, a[i] - a[i - 1]);

    while (m--) {
        char op[2];
        scanf("%s", op);

        if (op[0] == 'C') { // 修改
            int l, r, d;
            scanf("%d %d %d", &l, &r, &d);
            // 差分，在l处加上d,在r+1位置减去d
            add(l, d), add(r + 1, -d);
        } else {
            int l;
            scanf("%d", &l);
            // 方法1
            // printf("%lld\n", sum(l)); // 求前缀和
            // 推荐方法
            printf("%lld\n", a[l] + sum(l)); // 求前缀和
        }
    }
    return 0;
}