本题与我的树状数组进阶有类似之处,基本上思路完全一样
我们对(SS[i])进行分析
[S[i]=sum_{k=1}^{i} A[k]
]
[SS[i]=sum_{k=1}^{i} S[k]
]
[SS[i]=sum_{k=1}^{i} sum_{j=1}^{k} A[j]
]
[SS[i]=(i+1) * sum_{k=1}^{i} A[k] - sum_{k=1}^{i} A[k] * k
]
显然我们只需要维护两个树状数组,分别是(A[i]),(A[i]*i)的前缀和
[Code]
#include <bits/stdc++.h>
using namespace std;
int read(){
int x=0,flag=1; char c;
for(c=getchar();!isdigit(c);c=getchar()) if(c=='-') flag=-1;
for(;isdigit(c);c=getchar()) x=((x+(x<<2))<<1)+(c^48);
return x*flag;
}
const int N=1e5+50;
int n,m;
int a[N];
long long c1[N],c2[N];//c1:a[i]前缀和,c2:a[i]*i前缀和
int lowbit(int x) { return x&(-x); }
void update(int x,int y){
for(int i=x;i<=n;i+=lowbit(i)) c1[i]+=y,c2[i]+=1ll*y*x; //分别维护c1,c2
}
long long query(int x){
long long ret=0;
for(int i=x;i>0;i-=lowbit(i)) ret+=1ll*(x+1)*c1[i]-c2[i];//直接套公式计算
return ret;
}
int main() {
n=read(),m=read();
for(int i=1;i<=n;i++){
a[i]=read(); update(i,a[i]);
}
while(m--){
char s[105];
int x,y;
scanf(" %s %d",s,&x);
if(s[0]=='Q'){
printf("%lld
",query(x));
}
if(s[0]=='M'){
y=read();
update(x,y-a[x]);//差值更新
a[x]=y;
}
}
return 0;
}