可持久化数据结构板子整理（可持久化 线段树/字典树/可并堆）

静态序列查区间第k大

int update(int x,int l,int r,int k){
    int rt=++cnt;
    sum[rt]=sum[x]+1;
    L[rt]=L[x];
    R[rt]=R[x];
    if(l<r){
        if(k<=mid){
            L[rt]=update(L[rt],l,mid,k);
        }else{
            R[rt]=update(R[rt],mid+1,r,k);
        }
    }
    return rt;
}
int query(int xl,int xr,int l,int r,int k){
    if(l==r)return l;
    int x=sum[L[xr]]-sum[L[xl]];
    if(x>=k){
        return query(L[xl],L[xr],l,mid,k);
    }else{
        return query(R[xl],R[xr],mid+1,r,k-x);
    }
}

可持久化字典树

struct trie{
    int ch[2],siz,id;
}t[50000010];
void insert(int &now,int pre,int bit,long long val){
    now=++cnt;
    t[now]=t[pre];
    t[now].siz++;
    if(bit==-1){
        return;
    }
    int i=(val>>bit)&1;
    insert(t[now].ch[i],t[pre].ch[i],bit-1,id,val);
}
int query(int a,int b,int bit,long long val){
    if(bit<0){
        return 0;
    }
    int i=(val>>bit)&1;
    if(t[t[b].ch[!i]].siz-t[t[a].ch[!i]].siz>0){
        return (1<<bit)+query(t[a].ch[!i],t[b].ch[!i],bit-1,val);
    }else{
        return query(t[a].ch[i],t[b].ch[i],bit-1,val);
    }
}

可持久化可并堆

struct Heap{
    int ls,rs,dist;
    double w;
}tr[30000010];
int merge(int x,int y){
    if(!x||!y)return x+y;
    if(tr[x].w-tr[y].w>=eps)swap(x,y);
    int p=++tot;
    tr[p]=tr[x];
    tr[p].rs=merge(tr[p].rs,y);
    if(tr[tr[p].ls].dist<tr[tr[p].rs].dist)swap(tr[p].ls,tr[p].rs);
    tr[p].dist=tr[tr[x].rs].dist+1;
    return p;
}