[学习笔记]可持久化数据结构

可持久化学的很懵逼，是因为没有“由浅入♂深”的学习顺序，一上来就看主席树，让我们从最简单的开始。

可持久化线段树–访问历史版本

如题，你需要维护这样的一个长度为 N N 的数组，支持如下几种操作

在某个历史版本上修改某一个位置上的值
访问某个历史版本上的某一位置的值

修改一个点的内容只会修改一条链，所以logn这个大家肯定都懂。

我所理解的可持久化线段树就是新建一个节点在上面修改。
注意取地址符&的使用；
都是线段树的基本操作

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1000001;
int n,m,a[maxn],v,opt,loc,val;
int cnt,root[maxn];//线段树计数器;root[i]保存每个线段树的根 

struct Node{
int l,r,sum;
}tree[maxn*20]; 

void build_tree(int &rt,int l,int r)
{
    rt=++cnt;
if (l==r)
    {
        tree[rt].sum=a[l]; return;
    }
int mid=(l+r)>>1;
    build_tree(tree[rt].l,l,mid);
    build_tree(tree[rt].r,mid+1,r);
}

void insert(int &rt,int last,int l,int r,int x,int C)
{//rt当前根；last历史版本的线段树的根；x要修改的位置；C修改成的值 
    rt=++cnt; tree[rt]=tree[last];//复制这棵树 
if (l==r)
    {
        tree[rt].sum=C; return;
    }
int mid=(l+r)>>1;
if (x<=mid) insert(tree[rt].l,tree[last].l,l,mid,x,C);//再次递归的时候last会修改 
else insert(tree[rt].r,tree[last].r,mid+1,r,x,C);//last也要变 
}

int ques(int rt,int l,int r,int x)
{//last历史版本；last访问的位置 
if (l==r) return tree[rt].sum;
int mid=(l+r)>>1;
if (x<=mid) return ques(tree[rt].l,l,mid,x);
else return ques(tree[rt].r,mid+1,r,x);
}

int main()
{
scanf("%d%d",&n,&m);
for (int i=1; i<=n; i++) scanf("%d",&a[i]);
    build_tree(root[0],1,n);
for (int i=1; i<=m; i++)
    {
scanf("%d%d%d",&v,&opt,&loc);
if (opt==1)
        {
scanf("%d",&val);
            insert(root[i],root[v],1,n,loc,val);
        }
else
        {
printf("%d\n",ques(root[v],1,n,loc));
            root[i]=root[v];
        }
    }
return 0;
}

主席树–静态区间第k小

在可持久化线段树的基础之上进行权值线段树的相减；给初学者的忠告：这真的是非常简单易懂的代码模板，如果不懂的话就调试一下，注意递归调用时&的作用。

luogu
poj2104

//静态区间第K小
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=200007;

int n,m,x,y,k,a[maxn],loc[maxn],root[maxn],num[maxn],cnt;//cnt线段树的个数 
//loc数组用来保存排序之后数组和原数组的对应关系 ;root点所在的线段树的根 
struct Node{
int l,r,sum;//sum区间的长度 
}tree[maxn<<5];

bool cmp(int x,int y) {return a[x]<a[y];}

void insert(int &rt,int l,int r,int x)//复制一棵树，更新节点编号 
{
    tree[++cnt]=tree[rt]; rt=cnt;
    tree[rt].sum++;
if (l==r) return;
int mid=(l+r)>>1;
if (x<=mid) insert(tree[rt].l,l,mid,x);
else insert(tree[rt].r,mid+1,r,x);
}

int ques(int L,int R,int l,int r,int k)//第k小 
{
if (l==r) return l;
int mid=(l+r)>>1;
int t=tree[tree[R].l].sum-tree[tree[L].l].sum;
if (t>=k) return ques(tree[L].l,tree[R].l,l,mid,k);
else return ques(tree[L].r,tree[R].r,mid+1,r,k-t);//在右区间找t-k小的 
}

int main()
{
scanf("%d%d",&n,&m);
for (int i=1; i<=n; i++)
    {
scanf("%d",&a[i]); loc[i]=i;
    }
    sort(loc+1,loc+1+n,cmp);

for (int i=1; i<=n; i++)
        num[loc[i]]=i;//离散化后的数组，原来数值的大小已经不重要 
for (int i=1; i<=n; i++)
    {
        root[i]=root[i-1];
        insert(root[i],1,n,num[i]);
    }
for (int i=1; i<=m; i++)
    {
scanf("%d%d%d",&x,&y,&k);
int ans=ques(root[x-1],root[y],1,n,k);
printf("%d\n",a[loc[ans]]);//loc 
    }
return 0;
}

可持久化平衡树

您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作（对于各个以往的历史版本）：

插入x数
删除x数(若有多个相同的数，因只删除一个，如果没有请忽略该操作)
查询x数的排名(排名定义为比当前数小的数的个数+1。若有多个相同的数，因输出最小的排名)
查询排名为x的数
求x的前驱(前驱定义为小于x，且最大的数，如不存在输出-2147483647)
求x的后继(后继定义为大于x，且最小的数，如不存在输出2147483647)

和原本平衡树不同的一点是，每一次的任何操作都是基于某一个历史版本，同时生成一个新的版本。（操作3, 4, 5, 6即保持原版本无变化）

每个版本的编号即为操作的序号（版本0即为初始状态，空树）

#include<bits/stdc++.h>
using namespace std;
struct node
{
int l,r;int size,rnd,v;
}t[500005*50];
int cnt,rt[500005];
void update(int k)
{
    t[k].size=t[t[k].l].size+t[t[k].r].size+1;
}
void newnode(int &k,int x)
{
    t[k=++cnt].v=x;t[k].size=1;t[k].rnd=rand();
}
int merge(int a,int b)
{
if(!a||!b)return a+b;
if(t[a].rnd>t[b].rnd)
    {
int p=++cnt;t[p]=t[a];
        t[p].r=merge(t[p].r,b);
        update(p);return p;
    }
else
    {
int p=++cnt;t[p]=t[b];
        t[p].l=merge(a,t[p].l);
        update(p);return p;
    }
}
void split(int now,int k,int &x,int &y)
{
if(!now)x=y=0;
else
    {
if(t[now].v<=k)
        {
x=++cnt;t[x]=t[now];
split(t[x].r,k,t[x].r,y);
            update(x);
        }
else 
        {
y=++cnt;t[y]=t[now];
split(t[y].l,k,x,t[y].l);
            update(y);
        }
    }
}
void Delete(int &root,int w)
{
int x=0,y=0,z=0;
split(root,w,x,z);
split(x,w-1,x,y);
y=merge(t[y].l,t[y].r);
    root=merge(merge(x,y),z);
}
void Insert(int &root,int w)
{
int x=0,y=0,z=0;
split(root,w,x,y);
    newnode(z,w);
    root=merge(merge(x,z),y);
}
int getval(int k,int w)
{
if(w==t[t[k].l].size+1)return t[k].v;
else if(w<=t[t[k].l].size)return getval(t[k].l,w);
else return getval(t[k].r,w-t[t[k].l].size-1);
}
int getkth(int &root,int w)
{
int x,y;
split(root,w-1,x,y);
int ans=t[x].size+1;
    root=merge(x,y);
return ans;
}
int getpre(int &root,int w)
{
int x,y,k,ans;
split(root,w-1,x,y);
if(!x)return -2147483647;
    k=t[x].size;
    ans=getval(x,k);
    root=merge(x,y);
return ans;
}
int getnex(int &root,int w)
{
int x,y,ans;
split(root,w,x,y);
if(!y)return 2147483647;
else ans=getval(y,1);
    root=merge(x,y);
return ans;
}
int main()
{
int n,f,w,tim;
    scanf("%d",&n);
for(int i=1;i<=n;++i)
    {
        scanf("%d%d%d",&tim,&f,&w);
        rt[i]=rt[tim];
if(f==1)Insert(rt[i],w);
else if(f==2)Delete(rt[i],w);
else if(f==3)printf("%d\n",getkth(rt[i],w));
else if(f==4)printf("%d\n",getval(rt[i],w));
else if(f==5)printf("%d\n",getpre(rt[i],w));
else printf("%d\n",getnex(rt[i],w));
    }
return 0;
}

可持久化Tire树

这里以 bzoj3261 最大异或和为例
给定一个非负整数序列{a}，初始长度为N。有M个操作，有以下两种操作类型：
1、A x：添加操作，表示在序列末尾添加一个数x，序列的长度N+1。
2、Q l r x：询问操作，你需要找到一个位置p，满足l<=p<=r，使得：a[p] xor a[p+1] xor … xor a[N] xor x 最大，输出最大是多少。

考虑前缀和
sum[i]表示1.2….i的前缀的异或和，那么题目让求的就是sum[i]^sum[n]^x，选取一个i求其最大值.
每次就用X^=sum[n]，再用这样的X在L到R范围内找一个sum使其异或和最大
这就转化成了在一堆数里面选一个数与指定数异或和最大的经典trie树贪心的问题了

那么我们对于每一个新加的节点，都建立一棵tire树是不可以被接受的，类比上面可持久化线段树，主席树的思想，将sum[i]转化为二进制数，然后建立可持久化trie树，根据（sum[n]^x）在tire树上查找；贪心：尽量使异或和为1，不行的话为0；

对于相邻的两棵树，只有一个数不同而已，一个数在trie上对应的就是一条链，建树时我们沿着这条链走，把这条链构造进新树里，其余结构全部指向旧树
就是说新树只有这一条链的部分是新建的，而其他部分全部与旧树共享，类比主席树

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=600005;
const int sz=25;
int ans,num,n,m,x,y,k,cnt,tot,root[maxn],sum[maxn*30],ch[maxn*30][2];//tot异或和 ch[][]左右孩子 

void insert(int &now,int x,int dep)//now根 x当前的异或和，dep深度 
{
    sum[++num]=sum[now]+1;
    ch[num][0]=ch[now][0]; ch[num][1]=ch[now][1];
    now=num;
if (dep==-1) return;
int k=(x>>dep)&1;//x的第dep位是否为1；区分左右 
if (!k) insert(ch[now][0],x,dep-1);
else insert(ch[now][1],x,dep-1);
}

void ques(int L,int R,int x,int dep)
{
if (dep==-1) return;
int k=(x>>dep)&1;
if (sum[ch[R][k^1]]-sum[ch[L][k^1]]>0)
    {
        ans|=1<<dep;//或操作有加的一点意思(自行参悟)
        ques(ch[L][k^1],ch[R][k^1],x,dep-1);
    }
else ques(ch[L][k],ch[R][k],x,dep-1);
}

int main()
{
scanf("%d%d",&n,&m);
for (int i=1; i<=n; i++)
    {
scanf("%d",&x);
        tot^=x; root[i]=root[i-1];
        insert(root[i],tot,sz-1);
    }
    cnt=n;
for (int i=1;i<=m;++i)
    {
char opt=getchar();
while (opt!='A'&&opt!='Q') opt=getchar();
if (opt=='A')
        {
scanf("%d",&x);
            tot^=x; root[++cnt]=root[cnt-1];
            insert(root[cnt],tot,sz-1);
        }
else
        {
int l,r;
scanf("%d%d%d",&l,&r,&x);
            ans=0;
            --l,--r;l=max(l,0);r=max(r,0);
            ques(root[l-1],root[r],tot^x,sz-1);
if (l==0) ans=max(ans,tot^x);
printf("%d\n",ans);
        }
    }
return 0;
}

秒客网

[学习笔记]可持久化数据结构

可持久化线段树–访问历史版本

主席树–静态区间第k小

可持久化平衡树

可持久化Tire树

相关文章