• 线段树实现，PPT 上的写法

#include <bits/stdc++.h>
using namespace std;

struct SegmentTree {
	int n;
	vector<int> t;
	
	SegmentTree(int n_) {
		n = n_;
		t.assign(n * 2, 0);
	}
	
	// 把原数组的 a[p] += v;
	void update(int p, int v) {
		p += n;  // 把 p 变成 t 中的编号
		t[p] += v;
		for (int i = p / 2; i >= 1; i /= 2) {
			t[i] = t[i * 2] + t[i * 2 + 1];
		}
	}
	
	// 查询原数组 a[l], a[l + 1], ... a[r] 的和
	int query(int l, int r) {
		l += n, r += n;  // 把 l, r 变成 t 数组的下标
		int ans = 0;
		while (l <= r) {
			if (l % 2 == 1) ans += t[l], l++;
			if (r % 2 == 0) ans += t[r], r--;
			l /= 2, r /= 2;
		}
		return ans;
	}
};

int main() {
	int n, m, x, cmd, l, r, p;
	cin >> n >> m;
	SegmentTree seg(n);
	for (int i = 0; i < n; i++) {
		cin >> x;
		seg.update(i, x);  // 单点更新
	}
	
	while (m--) {
		cin >> cmd;
		if (cmd == 1) {
			cin >> p >> x;
			seg.update(p - 1, x);  // 单点更新
		} else {
			cin >> l >> r;
			cout << seg.query(l - 1, r - 1) << '\n';
		}
	}
	
	return 0;
}