【模板】【树状数组】

#include
using namespace std;
const int N = 5e5 + 5;
int a[N];//前缀和
int n, m;

int lowbit(int x)
{
	return x & -x;
}

void add(int x, int val)
{
	for (; x <= n; x += lowbit(x))//得到父节点
		a[x] += val;
}

int query(int x)
{
	int ans = 0;
	for (; x; x -= lowbit(x))//得到前缀区间
		ans += a[x];
	return ans;
}

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