BZOJ3155：Preprefix sum——题解

https://www.lydsy.com/JudgeOnline/problem.php?id=3155

最朴素的想法是两棵树状数组，一个记录前缀和，一个记录前缀前缀和，但是第二个我们非常不好修改

但其实我们发现$SS_i=i*a1+(i-1)*a2+…+ai$，我们可以试图构造这样的“类等差”数列，这样我们就可以通过加加减减就能做了。

为了照顾最后一位的查询，我们就维护$(n-i+1)*ai$吧！

于是我们修改就变成了两个单点修改了，查询也就是很简单了，$qry(x,1)-qry(x,0)*(n-x)$（前一个是第二棵树状数组，后面的是第一棵）。

#include<map>

#include<cmath>

#include<stack>

#include<queue>

#include<cstdio>

#include<cctype>

#include<vector>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

typedef long long ll;

const int N=1e5+;

inline int read(){

    int X=,w=;char ch=;

    while(!isdigit(ch)){w|=ch=='-';ch=getchar();}

    while(isdigit(ch))X=(X<<)+(X<<)+(ch^),ch=getchar();

    return w?-X:X;

}

int a[N],n,m;

ll tr[N][];

inline int lowbit(int t){return t&-t;}

inline void add(int x,ll y,int on){

    for(int i=x;i<=n;i+=lowbit(i))tr[i][on]+=y;

}

inline ll qry(int x,int on){

    ll res=;

    for(int i=x;i;i-=lowbit(i))res+=tr[i][on];

    return res;

}

int main(){

    n=read(),m=read();

    for(int i=;i<=n;i++){

    add(i,a[i]=read(),);

    add(i,(ll)(n-i+)*a[i],);

    }

    while(m--){

    char ch[];

    scanf("%s",ch);

    if(ch[]=='Q'){

        int x=read();

        printf("%lld\n",qry(x,)-qry(x,)*(n-x));

    }else{

        int x=read(),y=read();

        add(x,y-a[x],);

        add(x,(ll)(n-x+)*(y-a[x]),);

        a[x]=y;

    }

    }

    return ;

}