题解 P4868 【Preprefix sum】
SuperJvRuo
2018-08-31 22:39:05
来一篇树状数组的题解。
简化题意:
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;
}
```