题解 P4868 【Preprefix sum】

啊，看到这道题，可以自己手推一下这个前前缀和到底等于多少，其实很好推，而且长得很像另外一个式子 $s_x = \sum\limits_{i=1}^xa_i$ $ss_x = \sum\limits_{i=1}^x s_i= \sum\limits_{i=1}^x \sum\limits_{j=1}^i a_j $ 好了，最基本的式子就这么推出来了，但是发现这是个$O(n^2)$的玩意（口胡的时间复杂度），那么如何让它更快呢，我们可以继续化简 $\sum\limits_{i=1}^x \sum\limits_{j=1}^i a_j $ 在我们手动模拟时，我们可以发现$a_1$用了$x$次，$a_2$用了$x-1$次，$a_3$用了$x-2$次，然后可以推得 $a_i$用了$x-i+1$次 那么我们可以继续化简这个式子，把第二层的循环给他删掉 $\sum\limits_{i=1}^x a_i*(x-i+1) $ $\sum\limits_{i=1}^x a_i*(x+1)- \sum\limits_{i=1}^x a_i*i$ $(x+1)*\sum\limits_{i=1}^x a_i- \sum\limits_{i=1}^x a_i*i$ 那么整个式子就推到这里了，对于$x+1$这个常数，我们可以暂时不管，那么对于这个式子，我们可以得出一个信息 即用两个树状数组，一个维护$a_i$，一个维护$i*a_i$ 那么整个程序就可以打出来了，注意开long long，不然只有40分 ``` #include<bits/stdc++.h> using namespace std; const long long N=500051; long long lowbit(long long x){ return x&-x; } long long n,m; long long a[N]; long long c1[N]; long long c2[N]; void update(long long x,long long k){ long long i=x; for(;i<=N;i+=lowbit(i)){ c1[i]+=k; c2[i]+=x*k; } } void add(long long l,long long r,long long k){ update(l,k); update(r+1,-k); } long long res=0; long long ask(long long x){ res=0; long long i=x; for(;i;i-=lowbit(i)){ res+=(x+1)*c1[i]-c2[i]; } return res; } int main(){ scanf("%lld%lld",&n,&m); for(register long long i=1;i<=n;i++){ scanf("%lld",&a[i]); add(i,N,a[i]); } for(register long long i=1;i<=m;i++){ string op; long long x,y; cin>>op; scanf("%lld",&x); if(op[0]=='Q') printf("%lld\n",ask(x)); else{ scanf("%lld",&y); add(x,N,y-a[x]); a[x]=y; } } return 0; } ``` 但是我还是想讲一下其他的东西，如果对树状数组的入门的萌新来说，区间修改+区间查询的操作应该比较少见，我是想通过这篇题解讲解一下 假如是修改$[x,y]$区间，那么老样子，我们可以用差分的思想搞一下，即 ``` void add(int l,int r,int k){ update(l,k); update(r+1,-k); } ``` 这里我不会直接给出来update，因为和平时写的有变化，之后会讲 那么区间修改暂时先说到这里，如何去搞区间查询呢？ 肯定第一次都会想着直接$ask(r)-ask(l-1)$，但是是错的 原理是这样的没错，但是中间有一些细节需要处理 我们用$b[]$表示增量数组，例如$a[1]=1$，我让它加上一个$k$，那么$b[1]=k$ 继续推式子，由于刚刚的$ask(r),ask(l-1)$的运算法则应该是一样的，所以我们只以$ask(r)$为例子 $ask(r) = \sum\limits_{i=1}^xa_i$ $ask(r) = \sum\limits_{i=1}^x a_i= \sum\limits_{i=1}^x \sum\limits_{j=1}^i b_j $ 聪明的你此时一定会发现，跟这道题上面的式子简直那是一模一样，没错，包括后面的推理过程也是完全相同的，所以我就不继续写了，我就贴一下程序好了 ``` void update(int x,int k){ int i=x; for(;i<=n;i+=lowbit(i)){ tree1[i]+=k; tree2[i]+=x*k; } } void add(int l,int r,int k){ update(l,k); update(r+1,-k); } int res=0; int ask(int x){ res=0; int i=x; for(;i;i-=lowbit(i)){ res+=(x+1)*tree1[i]-tree2[i]; } return res; } int query(int l,int r){ return ask(r)-ask(l-1); } //区间改和区间查询 ``` 希望对大家有帮助