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

前置知识:主席树

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

# 洛谷 P3919

image-20210425201653739

# 题意

给定初始版本数组的 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;
}
更新于

请我喝[茶]~( ̄▽ ̄)~*

PocketCat 微信支付

微信支付

PocketCat 支付宝

支付宝