树状数组

#include <iostream>
using namespace std;

const int N = 500010;

int tree[N];  // 树状数组，tree[i] 管辖某个区间的和
int n;        // 数组大小

// lowbit(x)：x 的二进制中最低位的1及后面的0构成的值
// 例如：lowbit(6) = lowbit(110₂) = 2
int lowbit(int x) {
    return x & (-x);
    // x & (-x) 的原理：
    // -x 在二进制中等于 x 取反再加1
    // 与 x 做按位与后，只有最低位的1保留
}

// 单点修改：把原数组第 x 个元素加上 val
// 同时更新所有管辖范围包含 x 的 tree 节点
void update(int x, int val) {
    for (; x <= n; x += lowbit(x)) {
        // 每次跳到"父节点"：加上 lowbit(x)
        tree[x] += val;
    }
    // 为什么这样就能更新？tree[x] 管辖 [x-lowbit(x)+1, x]
    // x += lowbit(x) 跳到管辖更大区间的祖先节点
}

// 前缀和查询：求 a[1]+a[2]+...+a[x]
int query(int x) {
    int sum = 0;
    for (; x > 0; x -= lowbit(x)) {
        // 每次跳到"不重叠的前一段"
        sum += tree[x];
    }
    // 为什么这样就能求前缀和？
    // tree[x] 管辖 [x-lowbit(x)+1, x]
    // x -= lowbit(x) 跳到不重叠的前一段
    return sum;
}

// 区间求和：求 a[l]+a[l+1]+...+a[r]
// 利用前缀和的差：sum(l,r) = query(r) - query(l-1)
int rangeQuery(int l, int r) {
    return query(r) - query(l - 1);
}

int main() {
    int q;  // 操作次数
    cin >> n >> q;

    // 读入初始数组，逐个插入树状数组
    for (int i = 1; i <= n; i++) {
        int val;
        cin >> val;
        update(i, val);  // 把第 i 个位置加上 val
    }

    // 处理操作
    while (q--) {
        int op;
        cin >> op;
        if (op == 1) {
            // 修改操作：把第 x 个元素加上 y
            int x, y;
            cin >> x >> y;
            update(x, y);
        } else {
            // 查询操作：求第 l 到第 r 个元素的和
            int l, r;
            cin >> l >> r;
            cout << rangeQuery(l, r) << endl;
        }
    }
    return 0;
}