树状数组

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
//tr[]数组 为树状数组
int a[N], tr[N];
int n, m;
//返回末尾最后一个1和后面的0
int lowbit(int x) {
    return x & (-x);
}
//树状数组的+操作 将x位置上的数+上y
void add(int x, int y) {
    for (int i = x; i <= n; i += lowbit(i)) {
        tr[i] += y;
    }
}
//求和以 1到x区间的和
int get_sum(int x) {
    int res = 0;
    for (int i = x; i > 0; i -= lowbit(i)) {
        res += tr[i];
    }
    return res;
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        add(i, a[i]);
    }
    while (m--) {
        int k, x, y;
        cin >> k >> x >> y;
        if (k == 1) {
            add(x, y);
        }
        else if (k == 0) {
            cout << get_sum(y) - get_sum(x - 1) << endl;
        }
    }

    return 0;
}