可持久化Trie

最大异或和

记录sz

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
const int N=600010,M=25*N;
int n,m;
int s[N];
int tree[M][2],sz[M];
int root[N],cnt;
void insert(int k,int x,int pre,int &now)
{
    now=++cnt;
    if(k<0)
    {    
        sz[now]=sz[pre]+1;//注意可能有重复节点
        return;
    }
    int v=x>>k&1;//儿子
    tree[now][v^1]=tree[pre][v^1];
    insert(k-1,x,tree[pre][v],tree[now][v]);
    sz[now]=sz[tree[now][0]]+sz[tree[now][1]];//pushup
}
int query(int k,int x,int L,int R)
{
    if(k<0) return 0;
    int v=x>>k&1;
    int tmp=sz[tree[R][v^1]]-sz[tree[L][v^1]];
    if(tmp>0) return (1<<k)+query(k-1,x,tree[L][v^1],tree[R][v^1]);
    else return query(k-1,x,tree[L][v],tree[R][v]);
}
int main()
{
    scanf("%d%d",&n,&m);
    insert(23,0,0,root[0]);
    for(int i=1;i<=n;i++)
    {
        int x;
        scanf("%d",&x);
        s[i]=s[i-1]^x;
        insert(23,s[i],root[i-1],root[i]);
    }
    char op[2];
    int l,r,x;
    while(m--)
    {
        scanf("%s", op);
        if (op[0] == 'A')
        {
            scanf("%d",&x);
            n++;
            s[n]=s[n-1]^x;
            insert(23,s[n],root[n-1],root[n]);
        }
        else
        {
            scanf("%d%d%d",&l,&r,&x);
            printf("%d\n",query(23,s[n]^x,l==1?0:root[l-2],root[r-1]));////**l==1,r==1特判**
        }
    }
    return 0;
}

y总记录子树做靠右左节点

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
const int N=600010,M=25*N;
int n,m;
int s[N];
int tree[M][2],id[M];
int root[N],idx;
void insert(int i,int k,int pre,int &now)
{
    now=++idx;
    if(k<0)
    {
        id[now]=i;
        return;
    }
    int v=s[i]>>k&1;//儿子
    tree[now][v^1]=tree[pre][v^1];
    insert(i,k-1,tree[pre][v],tree[now][v]);
    id[now]=max(id[tree[now][0]],id[tree[now][1]]);
}
int query(int u,int k,int c,int l)
{
    int v=c>>k&1;
    if(k<0) return c^s[id[u]];
    if(id[tree[u][v^1]]>=l) return query(tree[u][v^1],k-1,c,l);
    else return query(tree[u][v],k-1,c,l);
}
int main()
{
    scanf("%d%d",&n,&m);
    id[0]=-1;
    insert(0,23,0,root[0]);
    for(int i=1;i<=n;i++)
    {
        int x;
        scanf("%d",&x);
        s[i]=s[i-1]^x;
        insert(i,23,root[i-1],root[i]);
    }
    char op[2];
    int l,r,x;
    while(m--)
    {
        scanf("%s", op);
        if (*op == 'A')
        {
            scanf("%d",&x);
            n++;
            s[n]=s[n-1]^x;
            insert(n,23,root[n-1],root[n]);
        }
        else
        {
            scanf("%d%d%d",&l,&r,&x);
            printf("%d\n",query(root[r-1],23,s[n]^x,l-1));
        }
    }
    return 0;
}

记录id方法非常局限，如果有多个限制条件通常不适用如 [TJOI2018]异或 推荐效仿主席树记录子树sz
可持久01Trie其实可以看成hjt主席树。
主席树区间维护值域我们通常传递[l,r]代表其维护区间
而对于01Trie我们通常传递(k)不妨假设维护区间为[l,r]那么它的左子树0维护区间为[l,r-x>>k&1]右子树1维护区间(r-x>>k&1,1]

主席树

第k小数
权值线段树维护区间内出现个数

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int N=100010;
vector<int> nums;
int n,m;
int root[N],cnt;
int a[N];
struct node
{
    int l,r,sum;
}tree[N*20];
int find(int x)
{
    return lower_bound(nums.begin(),nums.end(),x)-nums.begin()+1;
}
void insert(int l,int r,int pre,int &now,int pos)
{
    now=++cnt;
    tree[now]=tree[pre];
    tree[now].sum++;
    if(l==r) return;
    int mid=l+r>>1;

    if(pos<=mid) insert(l,mid,tree[pre].l,tree[now].l,pos);
    else insert(mid+1,r,tree[pre].r,tree[now].r,pos);
}
int query(int l,int r,int R,int L,int k)
{
    if(l==r) return l;
    int mid=l+r>>1;
    int tmp=tree[tree[R].l].sum-tree[tree[L].l].sum;
    if(k<=tmp) return query(l,mid,tree[R].l,tree[L].l,k);
    else return query(mid+1,r,tree[R].r,tree[L].r,k-tmp);
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        nums.push_back(a[i]);
    }
    sort(nums.begin(),nums.end());
    nums.erase(unique(nums.begin(),nums.end()),nums.end());

    for(int i=1;i<=n;i++) insert(1,nums.size(),root[i-1],root[i],find(a[i]));
    int l,r,k;
    while(m--)
    {
        cin>>l>>r>>k;
        cout<<nums[query(1,nums.size(),root[r],root[l-1],k)-1]<<endl;
    }
    return 0;
}

可持久化数组

洛谷可持久化数组
以下代码超时一个点（洛谷最后一个数据时间空间放大了结果A了

#include<bits/stdc++.h>

using namespace std;
using ll=long long;
template <class T=int> T rd()
{
    T res=0;T fg=1;
    char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') fg=-1;ch=getchar();}
    while( isdigit(ch)) res=(res<<1)+(res<<3)+(ch^48),ch=getchar();
    return res*fg;
}

const int N=1000010;
int a[N],n,m;
struct Array
{
    struct Segment
    {
        int l,r,v;
    }t[N*20];
    int rt[N],cnt;
    void build(int &u,int l,int r)
    {
        t[u=++cnt]={0,0,0};
        if(l==r) return t[u].v=a[l],void();
        int mid=l+r>>1;
        build(t[u].l,l,mid),build(t[u].r,mid+1,r);
    }
    void update(int &u,int pre,int l,int r,int pos,int v)
    {
        t[u=++cnt]=t[pre];
        if(l==r) return t[u].v=v,void();
        int mid=l+r>>1;
        if(pos<=mid) 
            update(t[u].l,t[pre].l,l,mid,pos,v);
        else
            update(t[u].r,t[pre].r,mid+1,r,pos,v);
    }
    int query(int u,int l,int r,int pos)
    {
        if(l==r) return t[u].v;
        int mid=l+r>>1;
        if(pos<=mid) 
            return query(t[u].l,l,mid,pos);
        else
            return query(t[u].r,mid+1,r,pos);
    }
}T;

int main()
{
    n=rd(),m=rd();
    for(int i=1;i<=n;i++) a[i]=rd();
    T.build(T.rt[0],1,n);
    for(int i=1;i<=m;i++)
    {
        int pre=rd(),op=rd(),pos=rd();
        if(op==1)
        {
            int v=rd();
            T.update(T.rt[i],T.rt[pre],1,n,pos,v);
        }
        else
        {
            printf("%d\n",T.query(T.rt[pre],1,n,pos));
            T.rt[i]=T.rt[pre];
        }
    }
    return 0;
}

可持久化并查集

洛谷可持久化并查集
可持久化数组+并查集按秩合并

#include<bits/stdc++.h>

using namespace std;

using pii=pair<int,int>;
constexpr int N(200005);
int n,m;

struct Array
{
    struct Segment
    {
        int l,r,v;
    }t[N*80];
    int rt[N],cnt;
    void build(int &u,int l,int r,int c)
    {
        t[u=++cnt]={0,0,0};
        if(l==r) 
        {
            if(c==1) t[u].v=l;
            else if(c==2) t[u].v=1;
            return;
        }
        int mid=l+r>>1;
        build(t[u].l,l,mid,c),build(t[u].r,mid+1,r,c);
    }
    void update(int &u,int pre,int l,int r,int pos,int v)
    {
        t[u=++cnt]=t[pre];
        if(l==r) return t[u].v=v,void();
        int mid=l+r>>1;
        if(pos<=mid) 
            update(t[u].l,t[pre].l,l,mid,pos,v);
        else
            update(t[u].r,t[pre].r,mid+1,r,pos,v);
    }
    int query(int u,int l,int r,int pos)
    {
        if(l==r) return t[u].v;
        int mid=l+r>>1;
        if(pos<=mid) 
            return query(t[u].l,l,mid,pos);
        else
            return query(t[u].r,mid+1,r,pos);
    }
    void clear(){cnt=0;}
    int inline get(int u,int pos){
        return query(rt[u],1,n,pos);
    }
    void inline ins(int u,int pos,int v)
    {
        update(rt[u],rt[u],1,n,pos,v);
    }
}sz,fa;
int find(int u,int x)
{
    int f=fa.get(u,x);
    return x==f?x:find(u,f);
}
bool inline merge(int v, int a, int b) {
    a=find(v,a),b=find(v,b);
    if(a==b) return false;
    int sa=sz.get(v,a),sb=sz.get(v,b);
    if (sa>sb) swap(a,b),swap(sa,sb);
    fa.ins(v,a,b);sz.ins(v,b,sa+sb);
    return true;
}
int main()
{
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);

    cin>>n>>m;
    fa.build(fa.rt[0],1,n,1);
    sz.build(sz.rt[0],1,n,2);

    int op,x,y;
    for(int i=1;i<=m;i++) 
    {
        cin>>op>>x;
        if(op==1)
        {
            cin>>y;
            fa.rt[i]=fa.rt[i-1];
            sz.rt[i]=sz.rt[i-1];
            merge(i,x,y);
        }
        else if(op==2)
        {
            fa.rt[i]=fa.rt[x];
            sz.rt[i]=sz.rt[x];
        }
        else 
        {
            cin>>y;
            int fx=find(i-1,x),fy=find(i-1,y);
            cout<<int(fx==fy)<<'\n';
            fa.rt[i]=fa.rt[i-1];
            sz.rt[i]=sz.rt[i-1];
        }
    }
    return 0;
}

以上代码纯属自用，记录下来方便复习。