可持久化线段树模板

指针查询

//查询第k小代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define pii pair<int, int>
#define QWQ return 0;
#define reg register

const int N=1e5+10;

struct segment_tree
{
    segment_tree *ls, *rs;
    int cnt;
    
    segment_tree():ls( nullptr ), rs( nullptr ), cnt( 0 ){}
    
    //构建空树
    static segment_tree *build( int l,int r )//静态函数，避免开临时变量节省空间 
	{
        segment_tree* node=new segment_tree();
        if( l == r ) return node;
        int mid=l+r>>1;
        node->ls=build( l,mid );
        node->rs=build( mid+1,r );
        return node;
    }

    //更新操作
    segment_tree *change( segment_tree *p,int l,int r,int x )
    {
        segment_tree *node=new segment_tree( *p );//复制前一版本节点
        node->cnt++;
        if( l == r ) return node;
        int mid=l+r>>1;
        if( x <= mid ) node->ls=p->ls->change( p->ls,l,mid,x );
        else           node->rs=p->rs->change( p->rs,mid+1,r,x );
        return node;
    }

    //查询第k小
    static int query( segment_tree *p,segment_tree *u,int l,int r,int k )
	{
        if( l == r ) return l;
        int cnt=u->ls->cnt-p->ls->cnt;
        int mid=l+r>>1;
        if( k <= cnt ) return query( p->ls,u->ls,l,mid,k );
        else           return query( p->rs,u->rs,mid+1,r,k-cnt );
    }
}*roots[N<<2];//存储各版本根节点

int a[N];

int main()
{
    ios::sync_with_stdio( false );
    cin.tie( nullptr ), cout.tie( nullptr );
    int n, m;
    cin>>n>>m;
    vector< int > uni;
    for( int i=1;i<=n;i++ ) cin>>a[i], uni.push_back( a[i] );
    sort( uni.begin(), uni.end() );
    uni.erase( unique( uni.begin(),uni.end() ),uni.end() );
    int siz=uni.size();
    roots[0]=segment_tree::build( 0,siz-1 );//初始化root[0]为空树，也是初始版的线段树 
    for( int i=1;i<=n;i++ )//构建各个版本的主席树
        roots[i]=roots[i-1]->change( roots[i-1],0,siz-1,lower_bound( uni.begin(),uni.end(),a[i] )-uni.begin() );
    for( int i=1, l, r, k;i<=m;i++ )
	{
        cin>>l>>r>>k;
        cout<<uni[segment_tree::query( roots[l-1],roots[r],0,siz-1,k )]<<"\n";
    }
    QWQ
}

---

动态数组模拟

//AtCoder Beginner Contest 453的问题 G - Copy Query
#include<bits/stdc++.h>
using namespace std;
#define QAQ return 
#define QWQ return 0;
#define ll long long
#define pii pair< int,int >

const int N=2e5+10;

int root[N];

struct segment_tree
{
    ll sum[N<<5];
	int ls[N<<5], rs[N<<5];
    int cnt;
    
    inline int new_node( int x )
    {
    	int p=++cnt;
    	sum[p]=sum[x];
        ls[p]=ls[x];
        rs[p]=rs[x];
        return p;
	}
	
	inline void pushup( int p ){ sum[p]=sum[ls[p]]+sum[rs[p]]; }
	
	inline int build( int l,int r )
	{
		int p=++cnt;
		if( l == r )
		{
			sum[p]=root[l];
			return p;
		}
		int mid=l+r>>1;
		ls[p]=build( l,mid );
		rs[p]=build( mid+1,r );
		pushup( p );
	}
	
	inline int change( int p,int l,int r,int pos,int x )
	{
		p=new_node( p );
		if( l == pos && r == pos )
		{
			sum[p]=x;
			return p;
		}
		int mid=l+r>>1;
		if( mid >= pos ) ls[p]=change( ls[p],l,mid,pos,x );
		else             rs[p]=change( rs[p],mid+1,r,pos,x );
		pushup( p );
		return p;
	}
	
	inline ll query( int p,int l,int r,int nl,int nr )
	{
		if( nl <= l && r <= nr ) return sum[p];
		int mid=l+r>>1;
		ll ans=0;
		if( mid >= nl ) ans+=query( ls[p],l,mid,nl,nr );
		if( mid <  nr ) ans+=query( rs[p],mid+1,r,nl,nr );
		return ans;
	}
	
}tree;

int main()
{
//	freopen( "txt.in","r",stdin );
//	freopen( "txt.out","w",stdout );
	ios::sync_with_stdio( false );
	cin.tie( nullptr ), cout.tie( nullptr );
	int n, m, q;
	cin>>n>>m>>q;
	for( int i=1, op, x, y, z;i<=q;i++ )
	{
		cin>>op>>x>>y;
		if( op == 1 )      root[x]=root[y];
		else if( op == 2 ) cin>>z, root[x]=tree.change( root[x],1,m,y,z );
		else               cin>>z, cout<<tree.query( root[x],1,m,y,z )<<"\n"; 
	}
	QWQ	 
}