前言
有没有发现，很多数据结构的前面加上一个 “可持久化”，难度就上了一两个档次？
本文就从基础的可持久化数组入门，同时解释可持久化的含义
例题引入
如题，你需要维护这样的一个长度为 N 的数组，支持如下几种操作
- 在某个历史版本上修改某一个位置上的值
- 访问某个历史版本上的某一位置的值
此外，每进行一次操作（对于操作 2，即为生成一个完全一样的版本，不作任何改动），就会生成一个新的版本。版本编号即为当前操作的编号（从 1 开始编号，版本 0 表示初始状态数组）
.
这道题如果没有 “可持久化” 的标签就是大水题……
不过题目要求维护一个称为 “历史版本” 的信息？
如果直接对每一个操作建一个数组显然 MLE 啊
可持久化
可持久化，是指所维护的信息可以持久地保留，不会被覆盖（修改）
普通的数组赋值、线段树、树状数组、平衡树等数据结构都是非持久化的，因为他们是直接在结构上修改维护的信息
那么可持久化的数据结构呢？当然是不直接在结构上修改维护的信息啦
我们通过新建结点的方式，避免修改历史的信息，同时能维护新的信息，这就是所谓的可持久化，那么历史版本其实就是把以前的信息保留下来了
新建结点
这是可持久化数据结构通用的操作。我们通过新建结点来维护新的信息
回到例题。由于题目中的修改是建立在某一个历史版本上的，因此什么时间戳维护的方法就行不通了
同时注意到，我们需要迅速通过版本号来找到对应的历史信息，而这个询问可能是涵盖整个数据结构的，因此我们的信息维护需要保证我们能根据版本号迅速找到整个历史数据结构的信息
所以，我们对原数组建立线段树
可持久化线段树基础
树的结构允许我们通过一个根结点以对数级别的时间复杂度访问任意一个信息，同时它的根结点可以代表整个结构。为什么？
只要我们建立好二叉树的左右儿子结点的指针，那么仅通过根结点作为入口，我们也能访问我们想访问的那个结点。因此，我们只需要处理好根结点与新建结点的维护，就能迅速通过不同版本的根结点访问到对应的数据结构
听起来有点玄乎？我们上图。首先对 建立线段树，而且什么都不用维护
接下来我们做一个修改操作：把第二个数修改为 5，那么结构会变成这样：
我们新建了绿色的结点和绿色的边，方框里代表的是不同版本的同一个结点
也就是说，我们使用不同编号的结点来表示某一位置的各个历史版本
19 号结点就是版本号 1 的根结点，那么如果我们要查询版本 1 的第 2 个数的值，就会顺着绿色的边找到 16 号结点；如果查询版本 1 的第 4 个数的值，就会顺着 的顺序找到 11 号结点。
如果我们又在版本 1 的基础上修改第 4 个数变成 10：
蓝色的新建结点构造了第 2 版本，如果我们查询第 2 版本下的第 2 个数，会沿着 找到 16 号结点，而非 9 号结点（因为我们的修改是建立在版本 1 的基础上的）
如果把版本 2 的线段树抽出来，大概是这样的：
理解以后就很好办了，我们查询的时候从对应版本的根结点查，修改的时候一路新建结点即可
可持久化线段树的实现
毕竟写法和普通线段树略有不同，我们讲一下实现的部分
从例题入手，先声明变量
| tot | a[i] | lc[u] | rc[u] | num[u] | ver[i] |
|---|---|---|---|---|---|
| 目前结点总数 | 初始时的序列 | 结点 u 的左子 | 结点 u 的右子 | 叶结点存的数值 | 版本 i 的根结点 |
树构建
和线段树差不多，区别在于每一次要新建结点：
void build(int &u,int l,int r){// 注意 u 是引用，可以对其赋值
u=++tot;// 新结点
if(l==r){num[u]=a[l];return;}// 到达叶结点
int mid=(l+r)>>1;
build(lc[u],l,mid),build(rc[u],mid+1,r);// 建立左子树和右子树
}
点修改
从根结点一路新建结点，到达叶结点就返回
需要注意的是，新的结点 也需要和它新建的子结点 连接，那么我们给修改函数一个返回值就行
int modify(int u,int pos,int val,int l,int r){//u 表示某一历史版本下的结点编号
int u2=++tot;// 给结点 u 新建不同版本的结点 u2
if(l==r)return num[u2]=val,u2;
int mid=(l+r)>>1;
if(pos<=mid)lc[u2]=modify(lc[u],pos,val,l,mid),rc[u2]=rc[u];//u2 的右子即 u 的右子
else lc[u2]=lc[u],rc[u2]=modify(rc[u],pos,val,mid+1,r);//u2 的左子即 u 的左子
return u2;// 返回结点 u 修改后的结点 u2 的编号，方便父结点对子结点的指针构建
}
点查询
跟着版本走啊
int query(int u,int pos,int l,int r){//u 表示某一历史版本下的结点编号
if(l==r)return num[u];
int mid=(l+r)>>1;
if(pos<=mid)return query(lc[u],pos,l,mid);
else return query(rc[u],pos,mid+1,r);
}
主函数
最后讲一下主函数的部分，毕竟涉及到 的维护以及上面两个函数的调用入口：
int main(){scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
build(ver[0],1,n);// 树构建
for(int i=1;i<=m;i++){
int vi,op,loc,val;
scanf("%d%d%d",&vi,&op,&loc);
if(op==1)scanf("%d",&val),ver[i]=modify(ver[vi],loc,val,1,n);
// 返回新建结点的编号，即为当前版本的根结点
else printf("%d\n",query(ver[vi],loc,1,n)),ver[i]=ver[vi];
// 直接指向该历史版本的根结点号
}
return 0;
}
Extra
上述可持久化线段树是支持动态单点修改，单点查询的
支持动态区间修改的就先咕着啦
主席树
2019.1.22 更新～
有一个经典的问题叫求区间第 k 小，对此有一个经典的解法叫主席树
主席树也是可持久化线段树的一种，不过也略有区别
下面给出问题的形式化定义
如题，给定 N 个整数构成的序列，将对于指定的闭区间查询其区间内的第 K 小值。
（不带修改操作，即静态查询）
.
这里我们直接讲解静态主席树的做法
权值线段树
对于普通的线段树，我们是以元素序列的下标为区间建立线段树，比如 表示的是 到 这一段元素的信息。
不过这里提出一种新的构建线段树的方式，即以值域为区间建立线段树，相同的数我们维护一个 cnt 记录出现的次数。比如对于序列 建立权值线段树如下：
每个结点代表一个值域区间，区间下面的数字表示在该区间内的数的个数
当然，对于 LuoguP3834 建立权值线段树需要离散化啦
那么这个权值线段树有什么用呢？考虑在这个东西上求整个序列的第 k 小。比如我们求整个序列的第 3 小值，那么就像 BST 的搜索一样，这颗权值线段树满足左小右大的原则，那么我们可以根据左子树与右子树的大小判断第 k 小数的位置。在上述示例中，我们沿这样的路径找到第 3 小值：
那么我们怎么实现区间查询呢
那就要引出可持久化权值线段树啦
可持久化权值线段树
这个其实就是主席树啦
我们引出这样一个问题：
如题，你需要维护这样的一个长度为 N 的序列 A，其中历史版本 i 是指 这一段子序列。
要求支持访问某个历史版本上的第 k 小值
.
感觉是不是很熟悉啊，在权值线段树上，一开始所有的 cnt 都为 0，作为版本 0.
我们把每一个数的插入都作为一个新的版本，新建结点保存更新的 cnt 值。
那么前 个数的第 k 小值其实就是在版本号为 r 的权值线段树上查询啦
不过，我们的区间可不是全部以 1 为端点的，那么应该怎么做呢
可持久化权值线段树的运算
这就要涉及到可持久化权值线段树的一些运算了。我们把上述示例建成可持久化权值线段树，是这样的：
结点中的数字由上到下分别表示结点编号，值域区间和 cnt 值. 一个方框内表示的是同一结点的不同版本，颜色越深的结点版本号越大：
建树结果是这样的：
那么这棵可持久化权值线段树有什么样的运算吗？
其实我们把问题转化一下，要求 中的第 k 小值，那么假设 对应的值域为 ，那么就相当于我们在权值线段树上查找值域为 中的第 k 小值
而权值线段树的查询可以转化为对左子右子树的大小的判断比较，因此问题转化为了，求 中元素属于值域 的元素的个数。
而我们知道 中元素属于 的元素的个数，可以通过查询第 r 个版本的权值线段树得到；
同理 中元素属于 的元素的个数，可以通过查询第 l-1 个版本的权值线段树得到，那么两者相减不就是 中元素属于 的元素的个数了吗！
综上，要查询 的第 k 小值，我们只需要找到可持久化权值线段树中第 l-1 个版本和第 r 个版本的权值线段树，那么两者对应结点的 cnt 值相减，就是 中元素属于对应区间的元素个数。
那么我们两边并列递归查询，直到值域区间只有一个数时，那么这个数就是第 k 小数啦
模板代码实现
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int N=2e5+5,LST=1<<23;
typedef pair<int,int> pii;
int n,m,tot;
int lc[LST],rc[LST],L[LST],R[LST],cnt[LST],rt[LST];
pii a[N];
bool cmp(pii a,pii b){return a.second<b.second;}
void pushup(int u){cnt[u]=cnt[lc[u]]+cnt[rc[u]];}
int build(int l,int r){// 返回对应的结点编号
int u=++tot,mid=(l+r)>>1;
L[u]=l,R[u]=r;
if(l<r)lc[u]=build(l,mid),rc[u]=build(mid+1,r);
return u;
}//build 建立的是 0 号版本的权值线段树
int modify(int u,int l,int r,int v){// 权值线段树的修改
int u2=++tot;
L[u2]=L[u],R[u2]=R[u];// 区间信息复制
if(l==r)return cnt[u2]=cnt[u]+1,u2;// 修改结点并返回
int mid=(l+r)>>1;
if(v<=mid)lc[u2]=modify(lc[u],l,mid,v),rc[u2]=rc[u];
else lc[u2]=lc[u],rc[u2]=modify(rc[u],mid+1,r,v);
pushup(u2);
return u2;
}
int query(int lu,int ru,int k,int l,int r){if(l==r)return l;// 找到那个数
int mid=(l+r)>>1,lcnt=cnt[lc[ru]]-cnt[lc[lu]];
if(k<=lcnt)return query(lc[lu],lc[ru],k,l,mid);
else return query(rc[lu],rc[ru],k-lcnt,mid+1,r);
}
int b[N];// 对应离散化前的值
int main(){scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&a[i].first),a[i].second=i;
sort(a+1,a+n+1);
int cur=0;// 表示离散化后的最大权值
for(int i=1;i<=n;i++){++cur,b[cur]=a[i].first;
while(a[i].first==a[i+1].first)a[i].first=cur,++i;
a[i].first=cur;
}
sort(a+1,a+n+1,cmp);
rt[0]=build(1,cur);// 初始时的树
for(int i=1;i<=n;i++)rt[i]=modify(rt[i-1],1,cur,a[i].first);
// 权值的范围是 [1,cur]，在上一个版本的基础上修改结点
for(int i=1,l,r,k;i<=m;i++){scanf("%d%d%d",&l,&r,&k);
printf("%d\n",b[query(rt[l-1],rt[r],k,1,cur)]);
}
return 0;
}
