树状数组

模板题：https://www.luogu.com.cn/problem/P3374
题解：

#include <bits/stdc++.h>

using namespace std;

const int N = 5e5 + 5;

int m, n;
int c[N];

int lowbit(int x) {
	return x & -x;
}
int query(int x) {
	int res = 0;
	while(x) {
		res += c[x];
		x = x - lowbit(x);
	}
	return res;
}
void add_x(int x, int val) {
	while(x < N) {
		c[x] += val;
		x = x + lowbit(x);
	}
}

int main() {
    cin >> m >> n;
    for(int i = 1; i <= m; i ++) {
        int ans;
        cin >> ans;
        add_x(i, ans);
    }
    int a, x, y;
    while(n --) {
        cin >> a >> x >> y;
        if(a == 1) {
            add_x(x, y);
        }
        else if(a == 2) {
            cout << query(y) - query(x - 1) << endl;
        }
    }
    return 0;
}