前前缀和(新颖的差分)

问题

给出一个序列\(a[i]\)

前缀和\(S=\sum\limits_{i=1}^{n}a[i]\)

前前缀和\(SS=\sum\limits_{i=1}^{n}S[i]\)

现在给出\(n\)个操作。一些是修改某个\(a[i]\),一些事查询某个\(SS[i]\)

手动分割线

\(S[i]=a[1]+a[2]+...+a[i]\)

\(SS[i]=S[1]+S[2]+...+S[i]\)

当修改某个\(a[i]\)为\(x\)时,对于\(S\)相当于时给区间\([i,n]\)都加上\(x-a[i]\)

对于\(SS\)而言，相当于给区间\([i,n]\)都加上\(k(x-a[i])\),其中\(k\)是常数,随着\(i\)的增加而增加

\(然后前面的都是废话，这题和S序列和差分都没有什么关系(手动滑稽)\)

实际上每次查询\(SS[i]\),答案就是原始的\(SS[i]\)加上期间在区间\([1,i]\)所做的操作的区间和

那么其实我们维护一下一个新的序列\(temp\),每次修改\(a[i]\)直接在上面做线段树修改就行。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=100009;
ll n,m;
ll e[maxn],s[maxn],sumn[maxn];
ll ss[maxn],ssumn[maxn],ans[maxn];
struct p{
    ll l,r,w,lazy;
}a[maxn*4];
void build(ll p,ll l,ll r){
    a[p].l=l,a[p].r=r;
    if(l==r){
        a[p].w=0;
        return;
    }
    ll mid=l+r>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    a[p].w=a[p<<1].w+a[p<<1|1].w;
}
void pushdown(int p){
    a[p<<1].lazy+=a[p].lazy;
    a[p<<1|1].lazy+=a[p].lazy;
    a[p<<1].w+=a[p].lazy*(a[p<<1].r-a[p<<1].l+1);
    a[p<<1|1].w+=a[p].lazy*(a[p<<1|1].r-a[p<<1|1].l+1);
    a[p].lazy=0;
}
void add(ll p,ll l,ll r,ll k){
    if(a[p].l>=l&&a[p].r<=r){
        a[p].lazy+=k;
        a[p].w+=k*(a[p].r-a[p].l+1);
        return;
    }
    pushdown(p);
    int mid=a[p].l+a[p].r>>1;
    if(mid>=l)   add(p<<1,l,r,k);
    if(mid<r)    add(p<<1|1,l,r,k);
    a[p].w=a[p<<1].w+a[p<<1|1].w;       
}
ll ssss=0;
void ask(ll p,ll l,ll r)
{
    if(a[p].l>=l&&a[p].r<=r){
        ssss+=a[p].w;
        return;
    }
    pushdown(p);
    ll mid=a[p].l+a[p].r>>1;
    if(mid>=l)   ask(p<<1,l,r);
    if(mid<r)    ask(p<<1|1,l,r);
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&e[i]);
        sumn[i]=e[i]+sumn[i-1];//i到n都修改k
        ssumn[i]=ssumn[i-1]+sumn[i];//i到n都修改(n-i)k 
    }
    build(1,1,n);
    for(int i=1;i<=m;i++)
    {
        string s;
        cin>>s;
        if(s[0]=='Q')
        {
            ssss=0;
            ll l;
            scanf("%lld",&l);
            ask(1,1,l);
            printf("%lld\n",ssss+ssumn[l]);
        }
        else
        {
            ll l,r;
            scanf("%lld%lld",&l,&r);
            ll k=r-e[l];
            add(1,l,n,k);
            e[l]=r;
        }
    }   
}