一切之始主席树https://blog.csdn.net/weixin_44879687/article/details/98186932

可持久化并查集
https://www.luogu.com.cn/problem/P3402
https://www.luogu.com.cn/blog/saisbook/solution-p3402
https://www.luogu.com.cn/blog/flashblog/solution-p3402

//首先可持久化并查集我们是用主席树来维护的，叶子节点维护每个位置的fa 
//维护2个量:每个点的父亲和每棵树的根节点的高度。 
//那么不使用路径压缩的话这个版本的主席树和上个版本的主席树
//有且只有一个点会被改动。
//那么就可以进行可持久化了。
//既然取消了路径压缩，为了保证复杂度，我们需要进行按秩合并。
//按秩合并其实就是，我们以树高为秩，每次将树高低的树合并到树高高的树上，
//那么对于树高高的树来说树高并没有变（也就说原树访问根节点的代价并没有变），而树高低的树访问根节点的代价只增加了\text{1}1（这棵树的根节点变成了树高高的树的儿子）。
//还有一种特殊情况那就是两棵树树高相同。
//这个时候把树A合并到树B上B的树高会增加1，而
//树A的高度则不会改变。 
//rta,rtb其实是a点和b点在主席树里的编号，depth指的是树高#include <bits/stdc++.h>const int N = 1e5 + 10;             
int n, m, i, j, k, cntu;  
int fa[N << 7], depth[N << 7], root[N << 1], lc[N << 7], rc[N << 7];   
int build(int l, int r) {//叶子节点维护每个位置的faint u = ++cntu;if (l == r) { fa[u] = l; return u; }int mid = (l + r) >> 1;lc[u] = build(l, mid);rc[u] = build(mid + 1, r);  return u;     
}
int query(int u, int l, int r, int x) {//寻找点x的父亲，找到x的叶子结点 if (l == r) return u;     int mid = (l + r) >> 1;if (x <= mid) return query(lc[u], l, mid, x);else return query(rc[u], mid + 1, r, x);
}
int update(int pre, int x, int y, int l, int r) {// u的父亲变了，用持久化方法构造 int u = ++cntu; lc[u] = lc[pre], rc[u] = rc[pre];      if (l == r) { fa[u] = y; depth[u] = depth[pre];//矮树并到高树，高度等于他 return u;}int mid = (l + r) >> 1;if (x <= mid) lc[u] = update(lc[pre], x, y, l, mid);else rc[u] = update(rc[pre], x, y, mid + 1, r);      return u;               
}
void add(int u, int l, int r, int x) {//在两棵树高度相等情况下，有棵树要+1 if (l == r) { depth[u]++; return; }int mid = (l + r) >> 1;if (x <= mid) add(lc[u], l, mid, x);else add(rc[u], mid + 1, r, x);  
}
int find(int v, int x) {//找到x在版本v的父亲 int y = query(root[v], 1, n, x);         if (fa[y] == x) return y;             return find(v, fa[y]);      
}int main() {scanf("%d %d", &n, &m);root[0] = build(1, n);for (int i = 1, op, a, b, v; i <= m; i++) {scanf("%d", &op), root[i] = root[i - 1];if (op == 1) {scanf("%d %d", &a, &b);int rta = find(i, a), rtb = find(i, b);       if (depth[rta] > depth[rtb]) std::swap(rta, rtb);//高度小的并到大的上 if (fa[rta] == fa[rtb]) continue;root[i] = update(root[i - 1], fa[rta], fa[rtb], 1, n);//版本更新  if (depth[rta] == depth[rtb]) add(root[i], 1, n, fa[rtb]);     } else if (op == 2) scanf("%d", &v), root[i] = root[v];else {scanf("%d %d", &a, &b);int rta = find(i, a), rtb = find(i, b);  puts(fa[rta] == fa[rtb] ? "1" : "0");}}return 0;   
}

可持久化字典树 区间
https://www.luogu.com.cn/blog/sdlang/Trie-study-text
https://www.cnblogs.com/Judge/p/9498797.html

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
#include <map>
#include <math.h>
#define ll long long
using namespace std; 
int cnt[1000010*31],c[1000010*31][2],tot,root[1000010];
int clone()
{tot++;c[tot][0]=c[tot][1]=0;return tot;
}
void insert(int last,int &now,int x)//类似主席树的思想  
{int tmp=now=clone();for(int i=27;i>=0;i--){int k=(x>>i)&1;c[tmp][k]=clone(),c[tmp][k^1]=c[last][k^1];//没有的连上和他前缀一样的别人tmp=c[tmp][k],last=c[last][k];//有的自己新建一个，cnt[tmp]=cnt[last]+1;//前缀个数+1 }//cnt[tmp]=cnt[last]+1;
}
int query(int l,int r,int x)
{int ans=0;for(int i=27;i>=0;i--){int k=(x>>i)&1;//printf("%d %d %d %d\n",cnt[c[r][k^1]],cnt[c[l][k^1]],c[r][k^1],c[l][k^1]);if(cnt[c[r][k^1]]>cnt[c[l][k^1]])//前缀个数相减 {ans+=(1<<i),r=c[r][k^1],l=c[l][k^1];//注意ans是+号。 }else {r=c[r][k],l=c[l][k];}}return ans;
}
int main()
{int n,q;scanf("%d%d",&n,&q);insert(0,root[0],0);int x,tmp=0;for(int i=1;i<=n;i++){scanf("%d",&x);tmp^=x;insert(root[i-1],root[i],tmp);}while(q--){char op ;cin>>op;if(op=='A'){n++;scanf("%d",&x);tmp^=x;insert(root[n-1],root[n],tmp);}else{int l,r,x;scanf("%d%d%d",&l,&r,&x);l--,r--;if (l == r && l == 0)printf("%d\n", tmp^ x);else printf("%d\n",query(root[max(l-1,0)],root[r],tmp^x));}}
}

树上可持久化字典树

//其实树上 可持久化 trie  和树上主席树类似，
//就是当前节点调用的 las 节点变成了该节点的父节点，
//查询的时候也是和树上主席树类似的套路， 
#include<cstdio>
#include<cstring>
#include<iostream>
#include<sstream>
#include<algorithm>
#define clr(a,b) memset(a,b,sizeof(a))
#define lson lr<<1,l,mid
#define rson lr<<1|1,mid+1,r
#define key_value ch[ch[root][1]][0]
#pragma comment(linker, "/STACK:102400000000,102400000000")
typedef  long long LL;
const LL  MOD = 1000000007;
const int N = 1e5+15;
const int maxn = 1e6+15;
const int letter = 130;
const int INF = 1e9;
const double pi=acos(-1.0);
const double eps=1e-10;
using namespace std;
inline int read()
{int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;
}
int n,q,head[N],tot,a[N];
int fa[N][18],deep[N],bin[18];
int ch[N*18][2],sum[N*18],root[N],cnt;
struct edges{int to,next;
}e[N<<1];
void addedges(int u,int v){e[tot].to=v,e[tot].next=head[u],head[u]=tot++;
}
int trie_insert(int x,int val){int tmp,y;tmp=y=++cnt;for(int i=16;i>=0;i--){ch[y][0]=ch[x][0],ch[y][1]=ch[x][1];sum[y]=sum[x]+1;//相等的前缀个数 int t=val&bin[i];t>>=i;x=ch[x][t];ch[y][t]=++cnt;y=ch[y][t];}sum[y]=sum[x]+1;return tmp;
}
int trie_query(int x,int y,int z,int val){int ans=0,ps=a[z];x=root[x],y=root[y],z=root[z];for(int i=16;i>=0;i--){int p=(val>>i)&1;//前缀个数满足条件 if(sum[ch[x][p^1]]+sum[ch[y][p^1]]-2*sum[ch[z][p^1]]>0){ x=ch[x][p^1],y=ch[y][p^1],z=ch[z][p^1];ans|=(1<<i);}else x=ch[x][p],y=ch[y][p],z=ch[z][p];}return max(ans,val^ps);
}
void dfs(int x,int g){root[x]=trie_insert(root[g],a[x]);for(int i=head[x];i!=-1;i=e[i].next){int to=e[i].to;if(to==g) continue;fa[to][0]=x;deep[to]=deep[x]+1;dfs(to,x);}
}
int lca(int x,int y){if(deep[x]<deep[y]) swap(x,y);int t=deep[x]-deep[y];for(int i=16;i>=0;i--) if(t&bin[i])x=fa[x][i];for(int i=16;i>=0;i--)if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];if(x==y) return x;return fa[x][0];
}
void init(){tot=cnt=0;clr(head,-1);deep[1]=0;clr(sum,0),clr(ch,0),clr(root,0),clr(fa,0);
}
int main(){int x,y,z,v;bin[0]=1;for(int i=1;i<=16;i++) bin[i]=bin[i-1]<<1;while(~scanf("%d%d",&n,&q)){init();for(int i=1;i<=n;i++) scanf("%d",a+i);for(int i=1;i<n;i++){scanf("%d%d",&x,&y);addedges(x,y),addedges(y,x);}fa[1][0]=0;dfs(1,0);for(int j=1;j<=16;j++)for(int i=1;i<=n;i++)fa[i][j]=fa[fa[i][j-1]][j-1];while(q--){scanf("%d%d%d",&x,&y,&v);z=lca(x,y);printf("%d\n",trie_query(x,y,z,v));}}return 0;
}