可持久化线段树

实现

#include <bits/stdc++.h>
#define mid (l+r>>1)
using namespace std;

const int N=1000005;
struct Node
{
	int ls,rs,val;
}G[N*25];
int a[N],root[N],cnt=0;
void build(int &u,int l,int r)
{
	u=++cnt;
	if(l==r){G[u].val=a[l];return;}
	build(G[u].ls,l,mid);
	build(G[u].rs,mid+1,r);
}
void update(int &u,int o,int l,int r,int x,int v)
{
	u=++cnt;
	G[u]=G[o];
	if(l==r){G[u].val=v;return;}
	if(x<=mid)update(G[u].ls,G[o].ls,l,mid,x,v);
	else update(G[u].rs,G[o].rs,mid+1,r,x,v);
}
int query(int u,int l,int r,int x)
{
	if(l==r)return G[u].val;
	if(x<=mid)return query(G[u].ls,l,mid,x);
	else return query(G[u].rs,mid+1,r,x);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	build(root[0],1,n);
	for(int i=1;i<=m;i++)
	{
		int v,op,x,y;
		cin>>v>>op;
		if(op==1)
		{
			cin>>x>>y;
			update(root[i],root[v],1,n,x,y);
		}
		else if(op==2)
		{
			cin>>x;
			root[i]=root[v];
			cout<<query(root[v],1,n,x)<<'\n';
		}
	}
	return 0;
}

例题

洛谷 P3919 【模板】可持久化线段树 1（可持久化数组）

洛谷 P3919 【模板】可持久化线段树 1（可持久化数组）

如题，你需要维护这样的一个长度为 $N$ 的数组，支持如下两种操作：

1. 在某个历史版本上修改某一个位置上的值。

2. 访问某个历史版本上的某一位置的值。

此外，每进行一次操作，就会生成一个新的版本。版本编号即为当前操作的编号（从 $1$ 开始编号，版本 $0$ 表示初始状态数组）。

对于操作 $2$，即为生成一个完全一样的版本，不作任何改动。即，询问生成的版本是询问所访问的那个版本的复制。

参考代码

#include <bits/stdc++.h>
#define mid (l+r>>1)
using namespace std;

const int N=1000005;
struct Node
{
	int ls,rs,val;
}G[N*25];
int a[N],root[N],cnt=0;
void build(int &u,int l,int r)
{
	u=++cnt;
	if(l==r){G[u].val=a[l];return;}
	build(G[u].ls,l,mid);
	build(G[u].rs,mid+1,r);
}
void update(int &u,int o,int l,int r,int x,int v)
{
	u=++cnt;
	G[u]=G[o];
	if(l==r){G[u].val=v;return;}
	if(x<=mid)update(G[u].ls,G[o].ls,l,mid,x,v);
	else update(G[u].rs,G[o].rs,mid+1,r,x,v);
}
int query(int u,int l,int r,int x)
{
	if(l==r)return G[u].val;
	if(x<=mid)return query(G[u].ls,l,mid,x);
	else return query(G[u].rs,mid+1,r,x);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	build(root[0],1,n);
	for(int i=1;i<=m;i++)
	{
		int v,op,x,y;
		cin>>v>>op;
		if(op==1)
		{
			cin>>x>>y;
			update(root[i],root[v],1,n,x,y);
		}
		else if(op==2)
		{
			cin>>x;
			root[i]=root[v];
			cout<<query(root[v],1,n,x)<<'\n';
		}
	}
	return 0;
}