树状数组

视频讲解: https://www.bilibili.com/video/BV1WDrnBPEKN/

维基百科: https://oi-wiki.org/ds/fenwick/#thetan-%E5%BB%BA%E6%A0%91

例题: https://www.luogu.com.cn/problem/P3374

#include <iostream>
#include <algorithm>
#include <cstring>
#include <stack>
#include <cmath>
#include <vector>
#include <queue>
#include <climits>

using namespace std;
typedef long long ll;

int n, m, a[600000], c[600000]; 

// 计算lowbit
int lowbit(int x) {
    return x & (-x);
}

// 计算前缀和
int query(int x) {
    int ans = 0;
    while (x > 0) {
        ans += c[x];
        x -= lowbit(x);
    }
    return ans;
}

// 从当前位置依次向后加x
void change(int pos, int delta) {
    while (pos <= n) {
        c[pos] += delta;
        pos += lowbit(pos);
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];

    // O(n) 建树
    for (int i = 1; i <= n; i++) {
        c[i] += a[i];
        int j = lowbit(i) + i;
        if (j <= n) c[j] += c[i];
    }

    for (int i = 1; i <= m; i++) {
        int tp, x, y;
        cin >> tp >> x >> y;
        if (tp == 1) {
            change(x, y); // 将位置 x 增加 y
        } else if (tp == 2) {
            // 区间和 = 前缀和(y) - 前缀和(x-1)
            cout << query(y) - query(x - 1) << endl;
        }
    }
    return 0;
}