题解 P4868 【Preprefix sum】

SuperJvRuo

2018-08-31 22:39:05

Solution

来一篇树状数组的题解。 简化题意: 1. 单点对$a_i$进行修改 2. 求$SS_i=\sum^i_{j=1}\sum^j_{k=1}a_k$ 分析: 展开$SS_i$,发现$SS_i=\sum^i_{j=1}(i-j+1)\times a_j$ 可以维护两个树状数组,一个维护$a_i$,另一个维护$b_i=(n-i+1)\times a_i$。这样,我们要查询的$SS_i$即为$\sum^i_{j=1}[(n-j+1)-(n-i)]\times a_j=\sum^i_{j=1}b_j-(n-i)\times\sum^i_{j=1}a_j$ 这里面的两个$\sum$都可以用树状数组$O(\log n)$求出。难度评级:普及+/提高 ``` #include<cstdio> #include<cctype> #define LL long long int Read() { int x=0;char c=getchar(); while(!isdigit(c)) { c=getchar(); } while(isdigit(c)) { x=x*10+(c^48); c=getchar(); } return x; } LL arr[100005];//存ai LL BIT[2][100005]; //BIT[0]为ai的BIT,BIT[1]为bi=(n-i+1)ai的BIT int n,m; int lowbit(int x) { return x&-x; } void Add(LL val,int pos,int idx) { for(int i=pos;i<=n;i+=lowbit(i)) BIT[idx][i]+=val; } void Modify(LL val,int pos) {//对两个BIT分别操作 Add(-arr[pos],pos,0); Add(-arr[pos]*(n-pos+1),pos,1); arr[pos]=val; Add(arr[pos],pos,0); Add(arr[pos]*(n-pos+1),pos,1); } LL Query(int pos) { LL ans=0;//sigma(bi) for(int i=pos;i;i-=lowbit(i)) { ans+=BIT[1][i]; } LL red=0;//sigma(ai) for(int i=pos;i;i-=lowbit(i)) { red+=BIT[0][i]; } return ans-red*(n-pos); } int main() { n=Read(),m=Read(); for(int i=1;i<=n;++i) { Add(arr[i]=Read(),i,0); Add(((LL)n-i+1)*arr[i],i,1); } char opt[10]; int pos; while(m--) { scanf("%s",opt); if(opt[0]=='M') { pos=Read(); Modify(Read(),pos); } else { printf("%lld\n",Query(Read())); } } return 0; } ```