线段树（单点修改）

原理

见《进阶指南》第210页。

模板题

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

#include <iostream>
#define ls rt << 1
#define rs rt << 1 | 1
using namespace std;

typedef long long LL;
const int N = 500010;
struct segmentTreeNode { // [l, r]
    int l, r;
    LL data;
    #define l(x) t[x].l
    #define r(x) t[x].r
    #define data(x) t[x].data
};
LL a[N];
segmentTreeNode t[N << 2];

void build (int rt, int l, int r) {
    l(rt) = l, r(rt) = r;
    if (l == r) {
        data(rt) = a[l];
        return;
    }
    int mid = l + r >> 1;
    build(ls, l, mid);
    build(rs, mid + 1, r);
    data(rt) = data(ls) + data(rs);
}
void modify (int rt, int idx, int val) { // a[idx] += val
    if (l(rt) == r(rt)) {
        data(rt) += val;
        return;
    }
    int mid = l(rt) + r(rt) >> 1;
    modify(idx <= mid ? ls : rs, idx, val);
    data(rt) = data(ls) + data(rs);
}
LL query (int rt, int l, int r) {
    if (l <= l(rt) && r(rt) <= r) return data(rt);
    int mid = l(rt) + r(rt) >> 1;
    LL res = 0;
    if (l <= mid) res += query(ls, l, r);
    if (r >= mid + 1) res += query(rs, l, r);
    return res;
}
    
int main () {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++ i) scanf("%lld", &a[i]);

    build(1, 1, n);
    for (int i = 1, opt; i <= m; ++ i) {
        scanf("%d", &opt);
        if (opt == 1) {
            int idx, val;
            scanf("%d%d", &idx, &val);
            modify(1, idx, val);
        } else {
            int l, r;
            scanf("%d%d", &l, &r);
            printf("%lld\n", query(1, l, r));
        }
    }
    return 0;
}