笛卡尔树太难了啊。

主席树

可持久化数据结构 \((\text {Persistent data structure)}\) 总是可以保留每一个历史版本，并且支持操作的不可变特性 \(\text{(immutable)}\)。

意思就是可以查询历史值，对于每一个历史版本 \(k\)，都是经过第 \(k-1\) 个版本、修改重连 \(\log n\) 个节点实现的。

如图，修改了 \([1,8]\) 中对应权值为 1 的结点，红色的点即为更改的点

只更改了 \(\log n\) 个结点，形成一条链，也就是说每次更改的结点数 = 树的高度。

注意主席树不能使用堆式存储法，就是说不能用 \(x\times 2，x\times 2+1\) 来表示左右儿子，而是应该动态开点，并保存每个节点的左右儿子编号。

所以我们只要在记录左右儿子的基础上，保存插入每个数的时候的根节点就可以实现持久化了。

例题

P3919 【模板】可持久化线段树 1

模板，单点修改单点查询的主席树。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+4;
int a[N];
int root[N];
int cnt;
struct PST{
	struct node{
		int ls,rs,val;
	}tr[N<<5];
	#define lid tr[now].ls
	#define rid tr[now].rs
	void build(int &now,int l,int r)
	{
		now=cnt++;
		if(l==r)
		{
			tr[now].val=a[l];return ;
		}
		int mid=(l+r)>>1;
		build(lid,l,mid),build(rid,mid+1,r);
	}
	void update(int pre,int &now,int l,int r,int &x,int &y,int &val)
	{
		now=cnt++;
		tr[now]=tr[pre];
		if(x<=l&&r<=y) 
		{
			tr[now].val=val;return ;
		}
		int mid=(l+r)>>1;
		if(x<=mid) update(tr[pre].ls,lid,l,mid,x,y,val);
		if(y>mid) update(tr[pre].rs,rid,mid+1,r,x,y,val);
	}
	int query(int now,int l,int r,int x,int y)
	{
		if(x<=l&&r<=y) return tr[now].val;
		int mid=(l+r)>>1;
		if(x<=mid) return query(lid,l,mid,x,y);
		if(y>mid)return query(rid,mid+1,r,x,y);
	}
}st;int n,m;
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	st.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;
			st.update(root[v],root[i],1,n,x,x,y);
		}
		else
		{
			cin>>x;
			int ans=st.query(root[v],1,n,x,x);
			root[i]=root[v];
			cout<<ans<<"\n";
		}
	}
}

P1652 可持久化线段树

把上面的码变一下，修改的时候再新建版本，其余不要动，加上区间查询即可。