Description
Input
第一行给出两个整数N，M。分别表示序列长度和操作个数
接下来一行有N个数，即给定的序列a1,a2,….an
接下来M行，每行对应一个操作，格式见题目描述
Output
对于每个询问操作，输出一行，表示所询问的SSi的值。
Sample Input
5 3
1 2 3 4 5
Query 5
Modify 3 2
Query 5
Sample Output
35
32
HINT
1<=N,M<=100000,且在任意时刻0<=Ai<=100000
Source
Katharon+#1
思路
学过线段树都知道树状数组不能处理区间修改，无逆元的区间加法
但是树状数组其实用差分可以做区间修改单点查询
当然这道题和更强的区间修改求和关系不大，但形式确实很像
对于原数列a1,a2,a3,a4…
a为 a1,a2,a3,a4…
S为 1*a1, 1*a1+1*a2, 1*a1+1*a2+1*a3…
SS为1*a1, 2*a1+1*a2, 3*a1+2*a2+1*a3…
比如 1 2 3 4 5 ，我们要求ss[3]
我们维护了 cp[3]=1+2+3
还维护了 cpp[3]=5*1+4*2+3*3
要 求3*1+2*2+1*3
就是 cpp[3]-2*cp[3] 2是由5-3得到的 （n-x）
所以ans=getsum(1,x)-getsum(0,x)*(n-x)
/**************************************************************
Problem: 3155
User: xlj
Language: C++
Result: Accepted
Time:480 ms
Memory:3240 kb
****************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define ll long long
using namespace std;
int n,m;
ll c[2][100005];
int a[100005];
int lowbit(int x){
return x&(-x);
}
void update(int p,int i,ll val){
for(int x=i;x<=n;x+=lowbit(x))
c[p][x]+=val;
}
ll getsum(int p,int i){
ll sum=0;
for(int x=i;x;x-=lowbit(x))
sum+=c[p][x];
return sum;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
update(0,i,a[i]);
update(1,i,(ll)(n-i+1)*a[i]);
}
for(int i=1;i<=m;i++)
{
char h[10];
int x,y;
scanf("%s",h);
if(h[0]=='M'){
scanf("%d%d",&x,&y);
update(0,x,y-a[x]);
update(1,x,(ll)(n-x+1)*(y-a[x]));
a[x]=y;
}
else {
scanf("%d",&x);
printf("%lld
",getsum(1,x)-getsum(0,x)*(n-x));
}
}
return 0;
}