可持久化
Ryan_
2019-10-08 20:06:20
# 可持久化线段树
我们经常会遇到这样的问题：我们需要维护一个数据结构，我们可以修改单一结点的值，查询单一结点的值，但是最关键的是我们可能还需要回退之前做过的某些操作。这里回退是指回到未做这些操作之前的状态。
在无回退操作的情况下，我们有大把的数据结构可供选择来解决这些问题。但是一旦涉及到回退操作，选择就少的多了。我们将支持回退操作的数据结构称为可持久化数据结构。
稍微思考一下如何可以在原来数据结构的基础上使其变得可持久化，有一个很简单的方案。我们每次操作都将重新建立一个新的数据结构，并将之前的操作都先在其上执行一次，之后执行该次操作。我们按操作执行顺序将这些数据结构维护成一个序列$S$，此时$S[0]$表示未经任何操作的初始数据结构。对于$i>0$，$S[i]$表示在S[0]的基础上执行过序号1到i的所有操作后得到的新的数据结构。在这样的做法下，我们称S[i]为版本i，回退操作等价于切换到某个特定版本。若操作i表示切换为版本j，那么我们可以直接将$S[i]$设置为$S[j]$的克隆。
上面提到的做法下很容易发现可以使得任意数据结构都可以支持回退操作，但是缺点也是非常明显，空间和时间的复杂度都奇高。每一次操作都需要累加之前操作的时间复杂度，空间也是，我们为了保存各个版本需要耗费大量的内存。
先说明时间复杂度的优化，对于i号操作，我们完全可以直接克隆版本$S[i-1]$并在其上执行i号操作，这样时间复杂度基本上就向空间复杂度看齐了。下面我们就可以专注于空间复杂度的优化（对应的也就是时间复杂度的优化）。
数据结构是用于保存数据的，我们将其保存数据的单元称为结点，我们可以利用结点来刻画整个数据结构的骨架。数据结构基本分为两类，一类是稳定的，一类是不稳定的。稳定的数据结构，其特定是在修改的结点的值之后不会改变结点之间的关系，而不稳定的数据结构在结点值变更后需要重新维护结点之间的关联。稳定的数据结构有线段树，后缀数组，前缀树等等，不稳定的数据结构主要就是各种二叉平衡树。对于稳定的树状结构，若孩子没有保存指向父结点的指针，即由父亲负责记录所有的孩子，我们很容易发现，当我们对某个结点更改时（修改值，新增，删除等操作），我们只需要同时修改该结点的所有祖先结点即可，那我们是不是也可以只克隆这些结点而非整个数据结构呢？答案是肯定的。由于父亲维护孩子，因此一个孩子允许有多个父亲，故所有没有被直接影响的结点都可以继续复用。我们将部分树状数据结构（特定是稳定和父亲维护父子关系）的一次操作的空间复杂度优化到了$O(h)$，其中h是树状数据结构的高度。
当我们将上面的想法作用到线段树时，就得到了常说的主席树。其高度为$O(log2(n))$，其中n为线段树维护的区间大小，同时其时间和空间复杂度均为$O(log2(n))$。
//转载自https://www.cnblogs.com/dalt/p/8324781.html
模板题[P3919 【模板】可持久化数组（可持久化线段树/平衡树）](https://www.luogu.org/problem/P3919)
```
#include<cstdio>
#define maxn 30000010
using namespace std;
int read(){
int x=0,f=1;char c=getchar();
while(c<'0' || c>'9'){
if(c=='-') f=-1;
c=getchar();
}
while(c>='0' && c<='9')
x=x*10+c-'0',c=getchar();
return x*f;
}
int n,m,cnt;
int tr[maxn],ll[maxn],rr[maxn],rt[maxn];
int build(int l,int r){
int root=++cnt;
if(l==r){
tr[root]=read();
return root;
}
int mid=(l+r)/2;
ll[root]=build(l,mid),rr[root]=build(mid+1,r);
return root;
}
int update(int pre,int l,int r,int a,int b){
int root=++cnt;//动态开点，防止报内存，不用去记录多余的空间
if(l==r){
tr[root]=b;
return root;
}
ll[root]=ll[pre],rr[root]=rr[pre];//新节点想原来节点的左右儿子分别建一条边
int mid=(l+r)/2;
if(a<=mid) ll[root]=update(ll[pre],l,mid,a,b);//更改左或右儿子为新建树链节点的儿子
else rr[root]=update(rr[pre],mid+1,r,a,b);
return root;
}
int fnd(int pre,int l,int r,int x){//线段树的常规操作
if(l==r) return tr[pre];
int mid=(l+r)/2;
if(x<=mid) return fnd(ll[pre],l,mid,x);
else return fnd(rr[pre],mid+1,r,x);
}
int main(){
n=read(),m=read();
build(1,n);
rt[0]=1;
for(int i=1;i<=m;i++){
int x=read(),bo=read();
if(bo==1){
int a=read(),b=read();
rt[i]=update(rt[x],1,n,a,b);
}
if(bo==2){
int a=read();
rt[i]=rt[x];
printf("%d\n",fnd(rt[x],1,n,a));
}
}
return 0;
}
```
# 主席树
主席树也是一棵可持久化线段树，常用的操作为求区间第K大。
注意：主席树是一棵值域线段树，看起来和平衡树很想。先考虑值域线段树，求整个区间的第K大？当然，我们把数据先离散化一边，在按期大小插入线段树中，比线段树区间的中值小，则往左边搜，反之向右边搜。这样第K大点就是在该点左边有k个数，简直和平衡树一模一样有木有！
主席树求的时区间第K大，相当于我们没1~i-1建立线段树，这就和可持久化挂边了。主要操作没什么，和可持久化线段树操作没什么区别
上题的主席树做法
```
#include<cstdio>
#define maxn 30000010
using namespace std;
int read(){
int x=0,f=1;char c=getchar();
while(c<'0' || c>'9'){
if(c=='-') f=-1;
c=getchar();
}
while(c>='0' && c<='9')
x=x*10+c-'0',c=getchar();
return x*f;
}
int n,m,cnt;
int tr[maxn],ll[maxn],rr[maxn],rt[maxn];
int build(int l,int r){
int root=++cnt;
if(l==r){
tr[root]=read();
return root;
}
int mid=(l+r)/2;
ll[root]=build(l,mid),rr[root]=build(mid+1,r);
return root;
}
int update(int pre,int l,int r,int a,int b){
int root=++cnt;
if(l==r){
tr[root]=b;
return root;
}
ll[root]=ll[pre],rr[root]=rr[pre];
int mid=(l+r)/2;
if(a<=mid) ll[root]=update(ll[pre],l,mid,a,b);
else rr[root]=update(rr[pre],mid+1,r,a,b);
return root;
}
int fnd(int pre,int l,int r,int x){
if(l==r) return tr[pre];
int mid=(l+r)/2;
if(x<=mid) return fnd(ll[pre],l,mid,x);
else return fnd(rr[pre],mid+1,r,x);
}
int main(){
n=read(),m=read();
build(1,n);
rt[0]=1;
for(int i=1;i<=m;i++){
int x=read(),bo=read();
if(bo==1){
int a=read(),b=read();
rt[i]=update(rt[x],1,n,a,b);
}
if(bo==2){
int a=read();
rt[i]=rt[x];
printf("%d\n",fnd(rt[x],1,n,a));
}
}
return 0;
}
```