Preprefix sum 差分+树状数组

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll c[100005],c2[100005];
ll a[100005];
ll n,m; 
#define lowbit(x) x&-x
void update(ll pos,ll x)
{
    for(register int i=pos;i<=n;i+=lowbit(i))
        c[i]+=x,c2[i]+=(pos-1)*x;
}
ll getsum(ll pos)
{
    register ll res=0;
    for(register int i=pos;i;i-=lowbit(i))
        res+=c[i]*(pos)-c2[i];
    return res;
}
int main()
{

	scanf("%lld %lld",&n,&m);
	for(int i=1;i<=n;i++){
		cin>>a[i]; 
		update(i,a[i]);
	}
	ll y,x;
	while(m--){
		string s;
		cin>>s;
		if(s[0]=='Q'){
		cin>>x;
		printf("%lld\n",getsum(x));
		}else {
			cin>>x>>y;
			update(x,y-a[x]);
			a[x] = y;
		}
	}
	return 0;
}