• 方法 3：将数组分块，$O(m \times \sqrt{n})$
• AC，100 分，但是代码略复杂

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	int n, m, cmd, x, k, l, r;
	cin >> n >> m;
	vector<int> a(n + 1);
	for (int i = 1; i <= n; i++) cin >> a[i];
	
	int d = sqrt(n);        // 每 d 个数分成一组
	int cnt = (n + 1) / d;  // 总共有 n / d 组
	
	vector<int> b(n + 1, 0);  // b[i]: a[i] 属于哪一组
	for (int i = 1, j = 1; i <= n; i++) {
		b[i] = j;
		if (i % d == 0) j++;
	}
	
	vector<int> s(cnt + 1, 0);  // s[i]: 第 i 组的数的和
	for (int i = 1; i <= n; i++) s[b[i]] += a[i];
	
	// 求 a[1] + a[2] + ... + a[r]
	auto sum = [&](int r) -> int {
		if (r == 0) return 0;
		int ans = 0;
		
		// r 前面整组的和
		for (int i = 1; i < b[r]; i++) ans += s[i];  // O(n / d)
		
		// r 所在的组的前部分的和
		for (int i = d * (b[r] - 1) + 1; i <= r; i++) ans += a[i];  // O(d)
		return ans;
	};
	
	// O(m * n)
	while (m--) {
		cin >> cmd;
		if (cmd == 1) {
			cin >> x >> k;
			a[x] += k, s[b[x]] += k;  // O(1))
		} else {
			cin >> l >> r;
			cout << sum(r) - sum(l - 1) << '\n';
		}
	}
	
	return 0;
}