P3374

#include <iostream>
#include <cmath>
#define int long long
using namespace std;
const int N = 5e5 + 7, S = sqrt(N + 7);
int n, m, loc[N], bl, s, Begin[S], End[S], l, r, op;
long long sum[S], a[N], tag[S], k;
void change (int l, int r, int k) {
	if (loc[l] != loc[r]) {
		for (int i = l; i <= End[loc[l]]; i ++) {
			a[i] += k;
			sum[loc[l]] += k;
		}
		for (int i = Begin[loc[r]]; i <= r; i ++) {
			a[i] += k;
			sum[loc[r]] += k;
		}
		for (int i = loc[l] + 1; i < loc[r]; i ++) {
			sum[i] += k * (End[i] - Begin[i] + 1);
			tag[i] += k;
		}
	} else {
		for (int i = l; i <= r; i ++) {
			a[i] += k;
			sum[loc[l]] += k;
		}
	}
}
long long query (int l, int r) {
	long long ans = 0;
	if (loc[l] != loc[r]) {
		for (int i = l; i <= End[loc[l]]; i ++)
			ans += a[i] + tag[loc[l]];
		for (int i = Begin[loc[r]]; i <= r; i ++)
			ans += a[i] + tag[loc[r]];
		for (int i = loc[l] + 1; i < loc[r]; i ++)
			ans += sum[i];
	} else
		for (int i = l; i <= r; i ++) ans += a[i] + tag[loc[l]];
	return ans;
}
int query1 (int rank) {
	return a[rank] + tag[loc[rank]];
}
signed main () {
	ios::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	cin >> n >> m;
	bl = sqrt(n);
	s = ceil(1.0 * n / bl);
	for (int i = 1; i <= n; i ++) {
		cin >> a[i];
		loc[i] = ceil(1.00 * i / bl);
	}
	for (int i = 1; i <= s; i ++) {
		Begin[i] = (i - 1) * bl + 1;
		End[i] = i * bl;
	}
	End[s] = n;
	for (int i = 1; i <= s; i ++)
		for (int j = Begin[i]; j <= End[i]; j ++)
			sum[i] += a[j];
	while (m --) {
		cin >> op;
		if (op == 1) {
			int x;
			cin >> x >> k;
			change(x, x, k);
		} else if (op == 2) {
			cin >> l >> r;
			cout << query(l, r) << '\n';
		}
	}
	return 0;
}

用这个模板修改了一下2过去了，1过不去。