题解 P4868 【Preprefix sum】
顾z
2018-10-26 20:20:19
# [顾](https://www.luogu.org/blog/RPdreamer/#)[z](https://www.cnblogs.com/-guz/)
~~你没有发现两个字里的blog都不一样嘛~~ qwq
显然,这是**差分+树状数组**
题目中给定的$a_i$就是我们的差分数组。
不会差分的小伙汁,来[这里](https://rpdreamer.blog.luogu.org/ci-fen-and-shu-shang-ci-fen)
安利很好的写树状数组的[博客](https://www.cnblogs.com/RabbitHu/p/BIT.html).
然后推一下式子.
如果我们修改差分数组$a_i$,显然,$S_i$会变化.
$S_i=S_{i-1}+a_i$
现在变成了
$S_i=S_{i-1}+x$
那么差值就变成了$x-a_i$
那么,我们就$add(i,x-a[i])$,不要忘了最后将$a_i$变为$x$
``代码``
```c++
#include<cstdio>
#include<algorithm>
#include<iostream>
#define int long long
#define R register
using namespace std;
inline void in(int &x)
{
int f=1;x=0;char s=getchar();
while(!isdigit(s)){if(s=='-')f=-1;s=getchar();}
while(isdigit(s)){x=x*10+s-'0';s=getchar();}
x*=f;
}
int n,m,last,t1[1000008],t2[1000008],a[1000008];
#define lowbit(x) x&-x
inline void add(int pos,int x)
{
for(R int i=pos;i<=n;i+=lowbit(i))
t1[i]+=x,t2[i]+=pos*x;
}
inline int query(int pos)
{
R int res=0;
for(R int i=pos;i;i-=lowbit(i))
res+=t1[i]*(pos+1)-t2[i];
return res;
}
char opt[8];
signed main()
{
in(n),in(m);
for(R int i=1,x;i<=n;i++)
{
in(a[i]);
add(i,a[i]);
}
for(R int i=1,x,y;i<=m;i++)
{
scanf("%s",opt+1);
if(opt[1]=='Q')
{
in(x);
printf("%lld\n",query(x));
}
else
{
in(x),in(y);
add(x,y-a[x]);
a[x]=y;
}
}
}
```
v