题解 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次，然后可以推得

那么我们可以继续化简这个式子，把第二层的循环给他删掉 $\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);
} 
//区间改和区间查询

希望对大家有帮助