树状数组 2

洛谷-P3368-【模板】树状数组 2

分析

见《进阶指南》第206页。

实现

#include <iostream>
using namespace std;

const int N = 500010;
int n, m;
int a[N], c[N];

int lowbit (int x) {
    return x & -x;
}
void add (int idx, int val) {
    while (idx <= n) {
        c[idx] += val;
        idx += lowbit(idx);
    }
}
int sum (int idx) {
    int res = 0;
    while (idx >= 1) {
        res += c[idx];
        idx -= lowbit(idx);
    }
    return res;
}

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

    add(1, a[1]);
    for (int i = 2; i <= n; ++ i) add(i, a[i] - a[i - 1]);

    for (int i = 1, opt; i <= m; ++ i) {
        scanf("%d", &opt);
        if (opt == 1) {
            int l, r, val;
            scanf("%d%d%d", &l, &r, &val);
            add(l, val);
            add(r + 1, -val);
        } else {
            int x;
            scanf("%d", &x);
            printf("%d\n", sum(x));
        }
    }
    return 0;
}