可持久化线段树

可持久化线段树，原名函数式线段树，由于创造者名字缩写是$HJT$，与我们敬爱的前国家主席名字缩写相同，于是我们尊称它为主席树，是最重要的可持久化数据结构之一

前置知识：动态开点线段树，权值线段树，线段树上二分

---

1.中心思想

在实际问题中，我们有时会需要开多棵线段树，而大多数时候空间是不支持我们开这么多棵完全不同的线段树的

回忆一下每次操作改变的点的数量，最多就$logn$个，这说明存在大量的相同的点，我们没必要再次建新点

于是我们采用只合并、添加一条链的方式来保存不同版本的线段树（所以限制死了动态开点），直接保存左右儿子的下标

---

2.例题及解决

这里直接拿最经典的题“区间第K小”举例子

首先想到使用权值线段树，在线段树上二分就可以算出第$k$小，注意到值域很大所以离散化

然后问题在于如何获得一个区间$[l,r]$的权值线段树，这里就需要主席树解决

首先建立$n$棵线段树，第$i$棵线段树表示区间$[1,i]$内所有值构成的权值线段树

那我们只需要将第$r$棵线段树“减去”第$l-1$棵线段树就行了，然后套线段树二分就能$AC$

但是我的指针线段树写的有点“优美”，请谨慎学习

#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
}

---

3.复杂度

每次修改都会创建$logn$个新节点，所以主席树的空间复杂度是$O(n+mlogn)$

而就本题而言，时间复杂度为离散化线段树+线段树上二分=$O((n+m)logn)$