树状数组

原理

见《进阶指南》第202页。

模板题

洛谷-P3374-【模板】树状数组 1

#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) { // a[idx] += val
    while (idx <= n) {
        c[idx] += val;
        idx += lowbit(idx);
    }
}
int sum (int idx) { // sum(a[1 ~ 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]);

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