# H. Ryuji doesn’t want to study (树状数组) [2018 ACM-ICPC Xuzhou Online Contest]

## 题面

### Description

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]$.

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]$($L$is the length of [ $l, r$ ] that equals to$r - l + 1$).

Now Ryuji has $q$ questions, you should answer him:

• If the question type is $1$, you should answer how much knowledge he will get after he reads books [ $l, r$ ].

• If the question type is $2$, Ryuji will change the $i$th book’s knowledge to a new value.

### Input

First line contains two integers $n$and$q$ ($n, q \le 100000$).

The next line contains n integers represent $a[i]$ $(a[i]≤1e9)$ .

Then in next $q$line each line contains three integers $a, b, c$, if $a = 1$, it means question type is $1$, and $b, c$represents [ $l , r$]. if $a = 2$, it means question type is$2$ , and$b, c$ means Ryuji changes the$b$th book’s knowledge to$c$ .

### Output

For each question, output one line with one integer represent the answer.

### Sample Output

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


### Sample Output

10
8


## 分析

$a[l] \times L + a[l+1] \times (L-1) + \cdots + a[r-1] \times 2 + a[r]$

• = $\sum\limits_{k=l}^{r}(r-l+1-(k-l)) \cdot a[k]$
• = $\sum\limits_{k=l}^{r}(r-k+1) \cdot a[k]$
• = $(r+1)\sum\limits_{k=l}^{r}a[k]-\sum\limits_{k=l}^{r}k \cdot a[k]$

## 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long ll;
#define LOWBIT(x) ((x) & -(x))

const int MAXN = 1e5 + 10;
ll a[MAXN];
ll c[MAXN], mc[MAXN];

ll ask(ll* ar, int x) {
ll ans = 0;
for( ; x; x -= LOWBIT(x)) ans += ar[x];
return ans;
}

void add(ll* ar, int x, ll y, int n) {
for( ; x <= n; x += LOWBIT(x)) ar[x] += y;
}

int main() {
ios::sync_with_stdio(false);
cin.tie(0);

int n = 0, q = 0;
while(cin >> n >> q) {
for(int i = 1; i <= n; i++)
cin >> a[i];

for(int i = 1; i <= n; i++)
for(int i = 1; i <= n; i++)
add(mc, i, a[i] * (ll)i, n);

for(int i = 1; i <= q; i++) {
int p = 0, l = 0, r = 0;
cin >> p >> l >> r;

if(p == 1) {
cout << (ll)(r + 1) * (ask(c, r) - ask(c, l - 1)) - (ask(mc, r) - ask(mc, l - 1)) << endl;
}
else if(p == 2) {