模板 主席树查询区间k小

模板：

有一个长$n$的序列，$m$个询问，每次查询区间$[l,r]$的第$k$小是多少

Solution:

可持久化线段树查询静态区间$k$小，利用可持久化线段树的多重线段树，以$O(n+nlogn)$的空间存储$n$棵线段树的特点，来保存一颗前缀权值线段树，随后在$[l,r]$的权值线段树上二分

思想：

不妨考虑一个简单问题，我们只查询序列的总体$k$小，并且限制使用权值线段树来解决问题，显然我们只需要在线段树上二分即可。那要查询$[l,r]$的区间$k$小，我们可以想办法构造出一颗$[l,r]$的权值线段树，直接在上面二分即可解决问题。

主席树就是利用这样的思想，$[l,r]$的权值线段树等价于$[1,r]$的权值线段树减去$[1,l-1]$的权值线段树，但是多棵线段树难以保存，并且维护每一棵线段树耗费时间巨大，每一棵都是$nlogn$，总复杂度至少就是$O(n^{2}logn)$，这是不理想的。可持久化线段树恰恰能保存多颗线段树于一身，并且添加一颗新的线段树时空复杂度都是$O(logn)$，所以可以保存所有的前缀权值线段树在一颗可持久化线段树上，这样只需要在$[1,l-1]$和$[1,r]$的差值权值线段树上二分即可。

而每次构建新的权值线段树，就是在$version[i-1]$的基础上在$a[i]$的位置上+1即可

二分：

在差值权值线段树上二分，如果左边的总数$\ge k$，那么直接在左边查询即可，否则查询右边的$k-tot$小，$tot$是左边子树的元素个数和

洛谷$P3834$

#include
#define ll long long
#define endl '\n'
using namespace std;

int version[1000005],tree[30000005],lson[30000005],rson[30000005];
int n,m,cnt,vp,a[1000005],b[1000005];
inline int& rs(int x){return rson[x];}
inline int& ls(int x){return lson[x];}

void build(int l,int r,int x)
{
    if(l==r) return;
    int mid=l+r>>1;
    if(!ls(x)) ls(x)=++cnt;
    if(!rs(x)) rs(x)=++cnt;
    build(l,mid,ls(x));
    build(mid+1,r,rs(x));
}

inline void push_up(int x){tree[x]=tree[ls(x)]+tree[rs(x)];}

void modify(int nl,int l,int r,int x,int nx)
{
    if(l==r){tree[nx]=tree[x]+1;return;}
    int mid=l+r>>1;
    if(nl<=mid) ls(nx)=++cnt,rs(nx)=rs(x),modify(nl,l,mid,ls(x),ls(nx));
    else ls(nx)=ls(x),rs(nx)=++cnt,modify(nl,mid+1,r,rs(x),rs(nx));
    push_up(nx);
}

void insert(int k)
{
    version[++vp]=++cnt;
    modify(k,1,n,version[vp-1],version[vp]);
}

int query(int l,int r,int lx,int rx,int k)
{
    if(l==r) return b[l];
    int mid=l+r>>1,tot=tree[ls(rx)]-tree[ls(lx)];
    if(k<=tot) return query(l,mid,ls(lx),ls(rx),k);
    return query(mid+1,r,rs(lx),rs(rx),k-tot);
}

inline int query(int l,int r,int k)
{
    return query(1,n,version[l-1],version[r],k);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin>>n>>m; 
    build(1,n,version[0]=++cnt);//不要写成build(1,n,1)，可以写成build(1,n,0)
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        b[i]=a[i];
    }
    sort(b+1,b+1+n);
    for(int i=1;i<=n;i++)
    {
        a[i]=lower_bound(b+1,b+1+n,a[i])-b;
        insert(a[i]);
    }
    while(m--)
    {
        int l,r,k; cin>>l>>r>>k;
        printf("%d\n",query(l,r,k));
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74