树状数组

基础模板 C++ 公开

#include <iostream>
#include <vector>

using namespace std;

int n, m;
long long tree[500005]; // 树状数组

// lowbit 函数：找到二进制最后一位 1
int lowbit(int x) {
    return x & -x;
}

// 单点修改：将第 x 个数加上 k
void add(int x, int k) {
    for (; x <= n; x += lowbit(x)) {
        tree[x] += k;
    }
}

// 前缀和查询：求出 [1, x] 的和
long long query(int x) {
    long long res = 0;
    for (; x > 0; x -= lowbit(x)) {
        res += tree[x];
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;

    // 初始化：读入初始值并建树
    for (int i = 1; i <= n; ++i) {
        int val;
        cin >> val;
        add(i, val); // 初始值视作在位置 i 加上 val
    }

    while (m--) {
        int type, x, y;
        cin >> type >> x >> y;
        if (type == 1) {
            add(x, y); // type 1: 将第 x 个数加上 y
        } else {
            // type 2: 查询区间 [x, y] 的和
            cout << query(y) - query(x - 1) << "\n";
        }
    }

    return 0;
}