TTM - To the moon ---- 用树状数组思想解可持久化线段树区间修改

· · 题解

此题其实就是可持久化线段树的区间修改。

可以用标记永久化。

但我不想用。

我用一种只用可持久化线段树的单点自增与区间求和来完成。

我们可以先想一下不可持久化该怎么只用这两个操作来完成。

也就是线段树 1。

再来看一下那两个操作。

那不就是树状数组吗？

众所周知，可以建两个树状数组，维护一个前缀和就可以顺利的解决线段树 1 的所有操作。

不清楚这种方法的，可以看这篇题解。

然后就是写两个可持久化线段树，维护一个前缀和。

然后记录每个时间戳对应的两个根。

在两棵树上查询就好啦。

代码可能有一点长，但总体还是很清晰的啦。

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
int n,m;
struct node{
    node *l,*r;
    int val;
}*root[2][signed(1e6)+10];
int tot[2];
node *null;
void _init(){
    tot[0]=tot[1]=0;
    null=new node;
    null->l=null->r=null;
    null->val=0;
}
node *build(int l,int r){
    if(l==r){
        node *p=new node;
        p->l=p->r=null;
        p->val=0;
        return p;
    }
    int mid=l+r>>1;
    node *p=new node;
    p->l=build(l,mid),p->r=build(mid+1,r);
    p->val=p->l->val+p->r->val;
    return p; 
}
void creat(){
    _init();
    root[0][tot[0]]=build(0,n);
    root[1][tot[1]]=build(0,n);
}
inline node *update(int x,int k,node *p,int l=0,int r=n){
    if(l==r && r==x){
        node *q=new node;
        q->l=q->r=null;
        q->val=p->val+k;
        return q;
    }
    node *q=new node;
    q->l=p->l,q->r=p->r;
    int mid=l+r>>1;
    if(x>=l && x<=mid) q->l=update(x,k,q->l,l,mid);
    if(x>mid && x<=r) q->r=update(x,k,q->r,mid+1,r); 
    q->val=q->l->val+q->r->val;
    return q;
}
inline int ask(int x,int y,node *p,int l=0,int r=n){
    if(l>=x && y>=r) return p->val;
    int mid=l+r>>1;
    int tot=0;
    if(x<=mid) tot+=ask(x,y,p->l,l,mid);
    if(y>mid) tot+=ask(x,y,p->r,mid+1,r);
    return tot;
}
int a[signed(1e6)+10],tim,s[signed(1e6)+10];
int w[signed(1e6)+10];
signed main() {
    cin>>n>>m;
    for(int i=1;i<=n;i++) a[i]=read(),s[i]=s[i-1]+a[i];
    creat();
    while(m--){
        char ch;
        cin>>ch;
        if(ch=='C'){
            int l=read(),r=read(),k=read();
            root[0][++tot[0]]=update(l,k,root[0][w[tim]]);
            root[0][tot[0]+1]=update(r+1,-k,root[0][tot[0]]),tot[0]++;
            root[1][++tot[1]]=update(l,l*k,root[1][w[tim]]);
            root[1][tot[1]+1]=update(r+1,-(r+1)*k,root[1][tot[1]]),tot[1]++;
            w[++tim]=tot[0];
        }
        if(ch=='Q'){
            int l=read(),r=read();
            int ans=s[r]+(r+1)*ask(0,r,root[0][w[tim]])-ask(0,r,root[1][w[tim]]);
            ans-=(s[l-1]+l*ask(0,l-1,root[0][w[tim]])-ask(0,l-1,root[1][w[tim]]));
            cout<<ans<<"\n";
        }
        if(ch=='H'){
            int l=read(),r=read(),t=read();
            int ans=s[r]+(r+1)*ask(0,r,root[0][w[t]])-ask(0,r,root[1][w[t]]);
            ans-=(s[l-1]+l*ask(0,l-1,root[0][w[t]])-ask(0,l-1,root[1][w[t]]));
            cout<<ans<<"\n";
        }
        if(ch=='B'){
            tim=read();
            root[0][++tot[0]]=root[0][w[tim]],root[1][++tot[1]]=root[1][w[tim]];
        }
    }
    return 0;
}

这种方法时间复杂度与空间复杂度都较高。

并且有点难理解。

可能遇见这种问题首选不是这种方法。