传说可以用树状数组，不过因为本人比较菜，于是上无脑差分数组+线段树。
容易发现，当一个数i增加x时，会使前缀和的前缀和j（j>=i）增加（j-i+1）*x。那么可以想象成i~n段加x，i+1~n段加x，i+2~n段加x……。
那么用差分数组就可以直接改i~n，然后可以求前缀和求答案。（前缀和的前缀和的差分前缀和？有点绕）
具体还是代码吧。语文死的早。
code：
#include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #define LL long long using namespace std; struct node{ int l,r,lc,rc; LL c,u; }tr[200010];int trlen=0; int n,m,a[100010]; LL sum[100010]; int bt(int l,int r) { int x=++trlen; tr[x].l=l;tr[x].r=r;tr[x].c=0;tr[x].u=0; if(l!=r) { int mid=(l+r)/2; tr[x].lc=bt(l,mid); tr[x].rc=bt(mid+1,r); } return x; } void update(int x) { int lc=tr[x].lc,rc=tr[x].rc;LL u=tr[x].u; tr[lc].c+=u*(LL)(tr[lc].r-tr[lc].l+1); tr[rc].c+=u*(LL)(tr[rc].r-tr[rc].l+1); tr[lc].u+=u;tr[rc].u+=u; tr[x].u=0; } void change(int x,int l,int r,LL c) { if(tr[x].l==l&&tr[x].r==r) { tr[x].u+=c; tr[x].c+=c*(r-l+1);return; } int mid=(tr[x].l+tr[x].r)/2,lc=tr[x].lc,rc=tr[x].rc; if(tr[x].u!=0) update(x); if(r<=mid) change(lc,l,r,c); else if(l>mid) change(rc,l,r,c); else change(lc,l,mid,c),change(rc,mid+1,r,c); tr[x].c=tr[lc].c+tr[rc].c; } LL findans(int x,int l,int r) { if(tr[x].l==l&&tr[x].r==r) return tr[x].c; int mid=(tr[x].l+tr[x].r)/2,lc=tr[x].lc,rc=tr[x].rc; if(tr[x].u!=0) update(x); if(r<=mid) return findans(lc,l,r); if(l>mid) return findans(rc,l,r); return findans(lc,l,mid)+findans(rc,mid+1,r); } int main() { scanf("%d %d",&n,&m);a[0]=0; for(int i=1;i<=n;i++) scanf("%d",&a[i]),sum[i]=(LL)a[i]; for(int i=1;i<=n;i++) sum[i]+=sum[i-1]; for(int i=1;i<=n;i++) sum[i]+=sum[i-1]; bt(1,n);change(1,1,1,sum[1]); for(int i=2;i<=n;i++) change(1,i,i,sum[i]-sum[i-1]); char s[5]; while(m--) { scanf("%s",s+1);int x,y; scanf("%d",&x); if(s[1]=='M') scanf("%d",&y),change(1,x,n,(LL)(y-a[x])),a[x]=y; else printf("%lld\n",findans(1,1,x)); } }