树状数组

重点
1. 思想：将区间值的维护转化为维护指令的累积影响
2. 两种特征：单点修改，区间查询，维护前缀和序列

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010, M = 100010;
typedef long long LL;
int n, m;
int a[N];
int b[N];

int lowbit(int x) {
    return x & -x;
}

void add(int x, int c) {
    for (int i = x; i <= n; i += lowbit(i)) b[i] += c;
}

int sum(int x) {
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) res += b[i];
    return res;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 0; i < m; i++) {
        char c[2];
        int l, r, d, x;
        scanf("%s", c);

        //cin >> c;
        if (c[0] == 'C') {
            scanf("%d%d%d", &l, &r, &d);
            add(l, d);
            add(r + 1, -d);
        } else {
            scanf("%d", &x);
            printf("%lld\n", (LL)sum(x) + a[x]);
        }
    }

    return 0;
}