서주 지역 사 이 버 전 Ryuji doesn 't want to study (트 리 배열)

Ryuji is not a good student, and he doesn't want to study. But there are n books he should learn, each book has its knowledge a[i]a[i].
Unfortunately, the longer he learns, the fewer he gets.
That means, if he reads books from ll to rr, he will get a[l] \times L + a[l+1] \times (L-1) + \cdots + a[r-1] \times 2 + a[r]a[l]×L+a[l+1]×(L−1)+⋯+a[r−1]×2+a[r](LL is the length of [ ll, rr ] that equals to r - l + 1r−l+1).
Now Ryuji has qq questions, you should answer him:
11. If the question type is 11, you should answer how much knowledge he will get after he reads books [ ll, rr ].
22. If the question type is 22, Ryuji will change the ith book's knowledge to a new value.
Input
First line contains two integers nn and qq (nn, q \le 100000q≤100000).
The next line contains n integers represent a[i]( a[i] \le 1e9)a[i](a[i]≤1e9) .
Then in next qq line each line contains three integers aa, bb, cc, if a = 1a=1, it means question type is 11, and bb, cc represents [ ll , rr ]. if a = 2a=2 , it means question type is 22 , and bb, cc means Ryuji changes the bth book' knowledge to cc
Output
For each question, output one line with one integer represent the answer.
샘플 입력 복사

5 3
1 2 3 4 5
1 1 3
2 5 0
1 4 5

샘플 출력 복사

10
8

           유지보수 (n + 1 - s) * a [s] 의 접두사 와 (ce 저장), 유지보수 a [s] 의 접두사 와 (c 저장);
           이렇게 특정한 (a, b) 의 총액 을 구 하 는 것 은 바로 sumce (b) - sumce (a - 1) - (n - b) * (sumc (b) - sumc (a - 1) 이다.

#include 
using namespace std;
#define ll long long int 
const int maxn = 100100;
ll ce[maxn], c[maxn], m[maxn];
int n, q;
int lowbit(int x) {
	return x&(-x);
}
ll get(int x,ll c[]) {
	ll sum = 0;
	while (x) {
		sum += c[x];
		x -= lowbit(x);
	}
	return sum;
}
void add(int x,ll d,ll c[]) {
	while (x <= n) {
		c[x] += d;
		x += lowbit(x);
	}
}
int main() {
	memset(ce, 0, sizeof(ce));
	memset(c, 0, sizeof(c));
	scanf("%d%d", &n, &q);
	for (int s = 1; s <= n; s++) {
		scanf("%lld", &m[s]);
		add(s, m[s], c);
		add(s, (n + 1 - s)*m[s], ce);
	}
	while (q--) {
		int a, b, d;
		scanf("%d%d%d", &a, &b, &d);
		if (a == 1) {
			ll ans1 = get(d, ce) - get(b-1, ce);
			ll ans2 = (get(d, c) - get(b-1, c))*(n - d);
			printf("%lld
", ans1 - ans2);
		}
		else {
			ll k = d - m[b];
			add(b, k, c);
			add(b, k*(n + 1 - b), ce);
			m[b] = d;
		}
	}
}