# 可持久化数组 (可持久化线段树)

前置知识：主席树
作用：记录下历史版本，可以进入历史版本进行修改或者查询

# 洛谷 P3919

# 题意

给定初始版本数组的 n 个数，之后 m 次操作，可以查询或者单点修改，每次查询或者修改都会产生一个新版本，查询产生一摸一样的版本，修改会产生一个只有一个位置不同的版本，版本数连续递增，输出每次查询某一个版本的某一个位置的数是几？

# 解法

原本想用 vector 开 n 个表示数组的每一个位置的不同版本，想的是每次只把一个数塞进要修改的 ve 里，不过这样会有问题。正解是可持续化数组，本质上就是一个保存历史版本的线段树，利用主席树的思想单点修改时只拉出来一条链保存修改过的信息。

# CODE

	#include <bits/stdc++.h>
	//#pragma G++ optimize(2)
	//#pragma G++ optimize(3,"Ofast","inline")
	#define debug freopen("in.txt","r",stdin); freopen("out.txt","w",stdout)
	#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
	using namespace std;
	typedef long long ll;
	typedef unsigned long long ull;
	const int MAXN=1e6+100;
	const int MOD=1e9+7;
	const int INF=0x3f3f3f3f;
	const int SUB=-0x3f3f3f3f;
	const double eps=1e-4;
	const double E=exp(1);
	const double pi=acos(-1);
	struct tree{
	int ls,rs,val;
	}hjt[MAXN*32];
	int arr[MAXN],rt[MAXN];
	int n,m,tot,cnt;
	int build(int l,int r){ // 首先建一个初始的树
	int root=++tot; // 分配空间
	if(l==r){
	hjt[root].val=arr[l]; // 到叶子节点就保存值
	return root;
	}
	int mid=l+r>>1;
	hjt[root].ls=build(l,mid); // 建造左子树
	hjt[root].rs=build(mid+1,r); // 建造右子树
	return root;
	}
	int insert(int pre,int pos,int val,int l,int r){
	int root=++tot;
	hjt[root]=hjt[pre];
	if(l==r){ // 单点修改
	hjt[root].val=val;
	return root;
	}
	int mid=l+r>>1;
	if(pos<=mid) hjt[root].ls=insert(hjt[pre].ls,pos,val,l,mid);
	else hjt[root].rs=insert(hjt[pre].rs,pos,val,mid+1,r);
	return root;
	}
	int query(int l,int r,int x,int pos){
	if(l==r) return hjt[x].val;
	int mid=l+r>>1;
	if(pos<=mid) return query(l,mid,hjt[x].ls,pos);
	else return query(mid+1,r,hjt[x].rs,pos);
	}
	int main(){
	ios;
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>arr[i];
	rt[cnt]=build(1,n);
	while(m--){
	int k,op,pos,val;
	cin>>k>>op;
	if(op==1){
	cin>>pos>>val;
	rt[++cnt]=insert(rt[k],pos,val,1,n);
	}
	else{
	cin>>pos;
	cout<<query(1,n,rt[k],pos)<<'\n';
	rt[++cnt]=rt[k]; // 直接复制过来之前的版本
	}
	}
	return 0;
	}

可持久化数组