主席树（可持久化权值线段树）

#include<bits/stdc++.h>
#define ll long long
#define N 200005
#define ls(x) tr[x].s[0]
#define rs(x) tr[x].s[1]
#define mid (l+r>>1)
using namespace std;

struct node
{
    int s[2],cnt;
}tr[N*22];
int root[N],tot;
void build(int &x,int l,int r)
{
    x=++tot;
    if(l==r) return;
    build(ls(x),l,mid);
    build(rs(x),mid+1,r);
}
void Insert (int x,int &y,int l,int r,int v)
{
    y=++tot;
    tr[y]=tr[x];
    tr[y].cnt++;
    if(l==r) return;
    if(v<=mid) Insert(ls(x),ls(y),l,mid,v);
    else Insert(rs(x),rs(y),mid+1,r,v);
}
int query(int x,int y,int l,int r,int k)
{
    if(l==r) return l;
    int s=tr[ls(y)].cnt-tr[ls(x)].cnt;
    if(k<=s) return query(ls(x),ls(y),l,mid,k);
    else return query(rs(x),rs(y),mid+1,r,k-s);
}
//离散化
vector<int> v;
int n,m,a[N],vn;
void work()
{
    for(int i=1;i<=n;i++)
    {
        scanf("%d",a+i);
        v.push_back(a[i]);
    }
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    vn=v.size();
}
int getid(int x)
{
    return lower_bound(v.begin(),v.end(),x)-v.begin()+1;
}
int main()
{
    scanf("%d%d",&n,&m);
    work();
    for(int i=1;i<=n;i++)
    {
        Insert(root[i-1],root[i],1,vn,getid(a[i]));
    }
    for(int i=1;i<=m;i++)
    {
        int l,r,k;
        scanf("%d%d%d",&l,&r,&k);
        int id=query(root[l-1],root[r],1,vn,k)-1;
        printf("%d\n",v[id]);
    }
    return 0;
}

可持久化数组

#include<bits/stdc++.h>
#define ll long long
#define N 1000005
#define ls(x) tr[x].s[0]
#define rs(x) tr[x].s[1]
#define mid (l+r>>1)
using namespace std;

struct node
{
    int s[2],v;
} tr[N*25];
int root[N],tot,a[N];
void build(int &x,int l,int r)
{
    x=++tot;
    if(l==r)
    {
        tr[x].v=a[l];
        return;
    }
    build(ls(x),l,mid);
    build(rs(x),mid+1,r);
}
void modify(int x,int &y,int l,int r,int k,int v)
{
    y=++tot;
    tr[y]=tr[x];
    if(l==r)
    {
        tr[y].v=v;
        return ;
    }
    if(k<=mid) modify(ls(x),ls(y),l,mid,k,v);
    else modify(rs(x),rs(y),mid+1,r,k,v);
}
int query(int x,int l,int r,int k)
{
    if(l==r) return tr[x].v;
    if(k<=mid) return query(ls(x),l,mid,k);
    else return query(rs(x),mid+1,r,k);
}
int n,m;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++) scanf("%d",a+i);
    build(root[0],1,n);
    for(int i=1; i<=m; i++)
    {
        int rt,op,x,y;
        scanf("%d%d%d",&rt,&op,&x);
        if(op==1)
        {
            scanf("%d",&y);
            modify(root[rt],root[i],1,n,x,y);
        }
        else
        {
            printf("%d\n",query(root[rt],1,n,x));
            root[i]=root[rt];
        }
    }
    return 0;
}

可持久化平衡树

#include<bits/stdc++.h>
#define ll long long
#define N 500005
#define ls(x) tr[x].s[0]
#define rs(x) tr[x].s[1]
using namespace std;
struct node
{
    int s[2],v,rnd,siz;
} tr[N*50];
int root[N],tot;
void newnode(int &x,int v)
{
    x = ++tot;
    tr[x].v=v;
    tr[x].rnd=rand();
    tr[x].siz=1;
}
void pushup(int p)
{
    tr[p].siz=tr[ls(p)].siz+tr[rs(p)].siz+1;
}
void split(int p,int v,int &x,int &y)
{
    if(!p)
    {
        x=y=0;
        return;
    }
    if(tr[p].v<=v)
    {
        x = ++tot;
        tr[x]=tr[p];
        split(rs(x),v,rs(x),y);
        pushup(x);
    }
    else
    {
        y = ++tot;
        tr[y]=tr[p];
        split(ls(y),v,x,ls(y));
        pushup(y);
    }
}
int Merge(int x,int y)
{
    if(!x||!y) return x+y;
    if(tr[x].rnd<tr[y].rnd)
    {
        rs(x)=Merge(rs(x),y);
        pushup(x);
        return x;
    }
    else
    {
        ls(y)=Merge(x,ls(y));
        pushup(y);
        return y;
    }
}
void Insert(int &root,int v)
{
    int x,y,z;
    split(root,v,x,y);
    newnode(z,v);
    root=Merge(Merge(x,z),y);
}
void del(int &root,int v)
{
    int x,y,z;
    split(root,v,x,z);
    split(x,v-1,x,y);
    y=Merge(ls(y),rs(y));
    root=Merge(Merge(x,y),z);
}
int getrank(int &root,int v)
{
    int x,y;
    split(root,v-1,x,y);
    int ans=tr[x].siz+1;
    root=Merge(x,y);
    return ans;
}
int getval(int root,int v)
{
    if(v==tr[ls(root)].siz+1)
        return tr[root].v;
    else if(v<=tr[ls(root)].siz)
        return getval(ls(root),v);
    else
        return getval(rs(root),v-tr[ls(root)].siz-1);
}
int getpre(int &root,int v)
{
    int x,y,s,ans;
    split(root,v-1,x,y);
    if(!x)return -2147483647;
    s=tr[x].siz;
    ans=getval(x,s);
    root=Merge(x,y);
    return ans;
}
int getnxt(int &root,int v)
{
    int x,y,ans;
    split(root,v,x,y);
    if(!y)return 2147483647;
    else ans=getval(y,1);
    root=Merge(x,y);
    return ans;
}
int main()
{
    int n,ver,op,v;
    scanf("%d",&n);
    for(int i=1; i<=n; ++i)
    {
        scanf("%d%d%d",&ver,&op,&v);
        root[i]=root[ver];
        if(op==1)Insert(root[i],v);
        else if(op==2)del(root[i],v);
        else if(op==3)printf("%d\n",getrank(root[i],v));
        else if(op==4)printf("%d\n",getval(root[i],v));
        else if(op==5)printf("%d\n",getpre(root[i],v));
        else printf("%d\n",getnxt(root[i],v));
    }
    return 0;
}