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

前置知识：主席树

作用：记录下历史版本，可以进入历史版本进行修改或者查询

洛谷P3919

image-20210425201653739

题意

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

解法

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

CODE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#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;
}