题目链接：https://nanti.jisuanke.com/t/31460
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 qq questions, you should answer him:
1. If the question type is 1, you should answer how much knowledge he will get after he reads books [ $l$, $r$ ].
2. If the question type is 2, Ryuji will change the ith 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] \le 1e9$).
Then in next qq 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 bth book' knowledge to $c$.
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$ 到 $n$，每本书权值为 $w[i]$，给出 $q$ 个操作，
操作 $1$，给出区间 $[l,r]$，则区间长度为 $L = r - l + 1$，查询的答案应为 $a[l] \times L + a[l+1] \times (L-1) + \cdots + a[r-1] \times 2 + a[r]$，
操作 $2$，把在编号为 $b$ 的书的权值改成 $c$。
题解：
线段树维护两个和：
一个是普通的区间和 $\sum\limits_{i = l}^r {w[i]} = w[l] + \cdots + w[r]$；
另一个是 $\sum\limits_{i = l}^r {\left[ {w[i] \times \left( {n - i + 1} \right)} \right]} = w[l] \times \left( {n - l + 1} \right) + \cdots + w[r] \times \left( {n - r + 1} \right)$。
那么，对于所有的查询：
$\begin{array}{l}
Q\left( {l,r} \right) \\
= w\left[ l \right] \times \left( {r - l + 1} \right) + w\left[ {l + 1} \right] \times \left( {r - l} \right) + \cdots + w\left[ r \right] \times 1 \\
= \sum\limits_{i = l}^r {\left[ {w\left[ i \right] \times \left( {r - i + 1} \right)} \right]} \\
= \sum\limits_{i = l}^r {\left[ {w\left[ i \right] \times \left( {n - i + 1 - n + r} \right)} \right]} \\
{\rm{ = }}\sum\limits_{i = l}^r {\left[ {w\left[ i \right] \times \left( {n - i + 1} \right) - w\left[ i \right] \times \left( {n - r} \right)} \right]} \\
= \sum\limits_{i = l}^r {\left[ {w\left[ i \right] \times \left( {n - i + 1} \right)} \right]} - \left( {n - r} \right)\sum\limits_{i = l}^r {w\left[ i \right]} \\
\end{array}$
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+; int n,q;
ll a[maxn]; /********************************* Segment Tree - st *********************************/
struct Node{
int l,r;
ll val,sum;
}node[*maxn];
void pushup(int root)
{
node[root].val=node[root*].val+node[root*+].val;
node[root].sum=node[root*].sum+node[root*+].sum;
}
void build(int root,int l,int r)
{
if(l>r) return;
node[root].l=l; node[root].r=r;
node[root].val=; node[root].sum=;
if(l==r)
{
node[root].val=a[l];
node[root].sum=a[l]*(n-l+);
}
else
{
int mid=l+(r-l)/;
build(root*,l,mid);
build(root*+,mid+,r);
pushup(root);
}
}
void update(int root,int pos,ll val)
{
if(node[root].l==node[root].r)
{
node[root].val=val;
node[root].sum=val*(n-pos+);
return;
}
int mid=node[root].l+(node[root].r-node[root].l)/;
if(pos<=mid) update(root*,pos,val);
if(pos>mid) update(root*+,pos,val);
pushup(root);
}
ll askval(int root,int st,int ed)
{
if(st>node[root].r || ed<node[root].l) return ;
if(st<=node[root].l && node[root].r<=ed) return node[root].val;
else return askval(root*,st,ed)+askval(root*+,st,ed);
}
ll asksum(int root,int st,int ed)
{
if(st>node[root].r || ed<node[root].l) return ;
if(st<=node[root].l && node[root].r<=ed) return node[root].sum;
else return asksum(root*,st,ed)+asksum(root*+,st,ed);
}
/********************************* Segment Tree - ed *********************************/ int main()
{
scanf("%d%d",&n,&q);
for(int i=;i<=n;i++) scanf("%d",&a[i]);
build(,,n);
for(int i=;i<=q;i++)
{
int type;
scanf("%d",&type);
if(type==)
{
int a,b;
scanf("%d%d",&a,&b);
ll A=asksum(,a,b);
ll B=askval(,a,b);
//cout<<A<<" "<<B<<endl;
printf("%lld\n",A-(n-b)*B);
}
else
{
int a; ll b;
scanf("%d%lld",&a,&b);
update(,a,b);
}
}
}