可持久化数据结构

ZHONGZIJIE0608 · 2024-07-16 14:05:01 · 个人记录

引言

查询区间第 k 小等需要维护历史版本的问题在生活中很常见，可持久化数据结构就是用来维护这种东西的。

简介

可持久化数据结构可以保留每个历史版本，并支持操作的不变性。

所有版本均可访问，但只有最新版可修改的称为部分可持久化。

所有版本均可访问和修改的称为完全可持久化。

用于几何计算（强制在线的扫描线），字串处理（大量重复字串），版本回溯等领域。

可持久化线段树

主席树的全称是可持久化权值线段树。

可持久化数组

维护一个历史版本全都可访问、修改的数组。数组长度与操作次数 1 \le N,M \le 10^6

一个不用脑子的算法就是对于每个版本维护一个数组。但是这样时空都是 O(N^2) 的，吃不消。

使用可持久化线段树。

注意到对于每个单点的修改，线段树上只修改 O(\log N) （树的高度）个点。考虑到区间修改下传标记常数太大，用标记永久化即可实现区间的可持久化。

这个东西类似于科幻电影中对“平行宇宙”的解释。对于每次操作（一般是修改）新建一个点，存储修改后的信息，那么原版就存储了历史信息。每次修改最多新开 O(\log N) 个结点，空间吃得消。

由于要新开大量节点，我们不能使用堆式存储法，即：

#define ls(x) (x<<1)
#define rs(x) (x<<1|1)

表示左右儿子是不行的。需要在每个节点中记录左右儿子的编号。

单点修改单点查询即可。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10;
struct KXFZ{int lc,rc,sm;}t[N*50];
int tot,rt[N*50];
void pushup(int x){t[x].sm=t[t[x].lc].sm+t[t[x].rc].sm;}
int upd(int ls,int pos,int val,int L,int R){
    int x=++tot;t[x]=t[ls];
    if(L==R){t[x].sm=val;return x;}
    int mid=(L+R)>>1;
    if(pos<=mid)t[x].lc=upd(t[x].lc,pos,val,L,mid);
    else t[x].rc=upd(t[x].rc,pos,val,mid+1,R);
    return x;
}
int qry(int x,int pos,int L,int R){
    if(L==R)return t[x].sm;
    int mid=(L+R)>>1;
    if(pos<=mid)return qry(t[x].lc,pos,L,mid);
    else return qry(t[x].rc,pos,mid+1,R);
}
int n,m;
signed main(){
    ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;++i){
        int x;cin>>x;
        rt[0]=upd(rt[0],i,x,1,n);
    }
    for(int i=1;i<=m;++i){
        int ver,op,loc,val;
        cin>>ver>>op>>loc;
        if(op==1)cin>>val,rt[i]=upd(rt[ver],loc,val,1,n);
        else {
            rt[i]=rt[ver];
            cout<<qry(rt[i],loc,1,n)<<'\n';
        }
    }
    return 0;
}

主席树

作为权值线段树，主席树有的时候一个点没有左儿子或右儿子。所以主席树一般会先建一棵空树。

剩下的部分就是可持久化了。

给你一个数组，求区间第 k 小值。

这是主席树的一个基本应用。

考虑把节点 R 作为版本，维护前缀 [1,R] 的每个数的出现次数，那么查询的时候看 [1,R] 和 [1,L-1] 的左儿子的和的差值 lcnt 是否大于 k。如果不是，说明区间的左儿子的个数是比 k 大的，否则更小。查询即可。

权值值域太大，记得要离散化。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
struct HJT{int lc,rc,sm;}t[N*50];
int rt[N*50],a[N],b[N],n,m,q,tot;
void pushup(int x){t[x].sm=t[t[x].lc].sm+t[t[x].rc].sm;}
int build(int L,int R){
    int x=++tot;t[x].sm=0;
    if(L==R)return x;int mid=(L+R)>>1;
    t[x].lc=build(L,mid);t[x].rc=build(mid+1,R);
    pushup(x);return x;
}
int upd(int ls,int pos,int val,int L,int R){
    int x=++tot;t[x]=t[ls];
    if(L==R){t[x].sm+=val;return x;}
    int mid=(L+R)>>1;
    if(pos<=mid)t[x].lc=upd(t[x].lc,pos,val,L,mid);
    else t[x].rc=upd(t[x].rc,pos,val,mid+1,R);
    pushup(x);return x;
}
int qry(int x,int ls,int L,int R,int k){
    if(L==R)return L;
    int mid=(L+R)>>1,lcnt=t[t[x].lc].sm-t[t[ls].lc].sm;
    if(k<=lcnt)return qry(t[x].lc,t[ls].lc,L,mid,k);
    else return qry(t[x].rc,t[ls].rc,mid+1,R,k-lcnt);
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;++i)cin>>a[i],b[i]=a[i];
    sort(b+1,b+1+n);m=unique(b+1,b+1+n)-b-1;
    rt[0]=build(1,m);
    for(int i=1;i<=n;++i)a[i]=lower_bound(b+1,b+1+m,a[i])-b,rt[i]=upd(rt[i-1],a[i],1,1,m);
    while(q--){
        int l,r,k;cin>>l>>r>>k;
        int pos=qry(rt[r],rt[l-1],1,m,k);
        cout<<b[pos]<<'\n';
    }
    return 0;
}

可持久化字典树

字典树

简要回顾下什么是字典树，怎样实现字典树。

定义

在字典树上，每个从根节点出发到达子节点的路径是一个字符串，每条边代表一个字符，出边按照字典序排列。

用途

用来记录字符串的公共前缀，可以减少大量匹配操作，高效查询公共前缀。

实现

struct trie{
    int nxt[1145141][31],cnt=0;//这是一个维护小写字母的 Trie.
    bool ext[1145141],usd[1145141];
    inline void insert(char *s,int l){
        int p=0;
        for(int i=0;i<l;++i){
            int c=s[i]-'a';
            if(!nxt[p][c])nxt[p][c]=++cnt;
            p=nxt[p][c];
        } 
        ext[p]=1;
    }
    inline int query(char *s,int l){
        int p=0;
        for(int i=0;i<l;++i){
            int c=s[i]-'a';
            if(!nxt[p][c])return 0;
            p=nxt[p][c];
        }
        if(usd[p])return 2;
        else if(ext[p])return usd[p]=1;
        else return 0;//维护该串是否存在及是否被重复访问。
    }
}t;

可持久化字典树

可持久化 Trie 树和可持久化线段树类似，每次只修改被添加或者值被改动的结点，在上一版本的基础上连边，使得最后每个版本的树根遍历所能分离出的字典树都是完整且包含全部信息的。

在大部分的可持久化 Trie 的题目中，Trie 一般是以 01-Trie 形式出现的。

01-Trie 可以很方便地维护异或最值，异或和等操作。

对于一个长度为 n 的数组 a 维护以下操作：

在数组末尾添加一个数 x，n 的值加上 1。

给出查询区间 [l,r] 和一个值 k，在 [l,r] 中查找一个位置 p，使得k \oplus \bigoplus_{i=p}^n a_i 最大。

\texttt {Link}

求区间异或和很麻烦，考虑前缀和优化变成 k \oplus s_n \oplus s_{p-1} 最大。s_i=\bigoplus_{j=1}^{i}a_j

不难发现 k \oplus s_n 是定值，令其为 val。

原题变成 val \oplus s_{p-1} 最大。

用可持久化字典树。

下面是一个板子。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=6e5+10;
int n,m;
struct P_01Trie{
    int rt[N],sm,top,sz,ch[2][N*50],cnt[N*50],v[N];
    void ins(int val){
        rt[++top]=++sz;v[top]=val;
        int l=rt[top-1],r=rt[top];
        for(int i=24;i>=0;--i){
            int b=((val>>i)&1);
            ch[b^1][r]=ch[b^1][l];
            ch[b][r]=++sz;
            l=ch[b][l],r=ch[b][r];
            cnt[r]=cnt[l]+1;
        }
    }
    int qry(int val,int l,int r){
        int ans=0;l=rt[l],r=rt[r];
        for(int i=24;i>=0;--i){
            int b=((val>>i)&1);
            if(cnt[ch[b^1][r]]>cnt[ch[b^1][l]]){
                ans+=(1<<i);b^=1;
            }l=ch[b][l],r=ch[b][r];
        }
        return ans;
    }
}tr;
signed main(){
    ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
    cin>>n>>m;tr.ins(0);
    for(int i=1,x;i<=n;++i)cin>>x,tr.ins(tr.sm^=x);
    while(m--){
        char op;cin>>op;int x,l,r;
        if(op=='A')cin>>x,tr.ins(tr.sm^=x);
        else cin>>l>>r>>x,--l,cout<<tr.qry(tr.sm^x,l,r)<<'\n';
    }
    return 0;
}

总算是跳出来了，爆了一个小时了……

可持久化平衡树

咕咕咕

可持久化可并堆

咕咕咕