• 最牛逼的方法，树状数组，$O(m \times log(n))$
• AC，100 分，又快又好写！！

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

using i64 = long long;

template <typename T>  // 使用 template 模板, 用法见定义
struct Fenwick {
	int n;
	vector<T> a;
	
	Fenwick(int n_) : n(n_) {
		// 注意: 树状数组都是从 1 开始编号 a[1..n], 不要从 0 开始
		// 相当于 a = vector<int>(n + 1, 0)
		a.assign(n + 1, 0);
	}
	
	// 更新操作, 不断 p += lowbit(p)
	void add(int p, T v) {
		for (; p <= n; p += p & -p) a[p] += v;
	}
	
	// 求前缀和: sum(a[1..p]), 不断 p -= lowbit(p)
	T get(int p) {
		T ans = 0;
		for (; p > 0; p -= p & -p) ans += a[p];
		return ans;
	}
	
	// 求区间和: sum(a[1..r]) - sum(a[1..(l-1)])
	T get(int l, int r) {
		return get(r) - get(l - 1);
	}
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	int n, m, x, y, z;
	cin >> n >> m;
	
	// 利用 template, 申明为 int 的树状数组
	// Fenwick<int> 可以申明为 int 的树状数组
	Fenwick<int> a(n);
	for (int i = 1; i <= n; i++) {
		cin >> x;
		a.add(i, x);
	}
	
	while (m--) {
		cin >> x >> y >> z;
		if (x == 1) a.add(y, z);           // 更新
		else cout << a.get(y, z) << '\n';  // 求前缀和
	}
	
	return 0;
}