主席树的简要讲解-摩杜云开发者社区

区间第k小值

主席树是解决动态查找序列上[l,r]区间中的第k小值的一个数据结构

核心思想:动态开点（后面会讲）
传统线段树都是值域线段树
其实意思就是每个节点都存的是序列上[l,r]的一个区间和，但是考虑我们需要动态处理区间的不是最值，故换一种线段树

主席树一般用的是权值线段树
就是把[l,r]改为[min(a),max(a)] a是序列A在[l,r]区间里的一个子序列，每个节点下都保存一个统计数字s,代表在当前权值域里，有多少个数字
array : 1 4 3 3

           [1,4]
           s = 4
    [1,2]         [3,4]
    s = 1         s = 3
[1,1]  [2,2]    [3,3] [4,4]
s = 1  s = 0    s = 2  s = 1

(不会画图QWQ)

步入正题
我们转换思想，每一次开点都存储一个版本的权值线段树，但是这样会让空间复杂度直线上升为O(n^2)，这是不能容忍的
但是我们再想
这是一颗树性结构，我们每一次加点都只会改变上下log n个点的数据，为什么我们就不能每一次都开一个log n的新点，将与这次更改无关的点直接开一条新边连接到新点呢？

不能像上一个那样形似了，我直接盗图

这是第一个版本在insert(4)后的结果
每一次insert都存储一个root[i+1]，表示第i+1个版本的根节点

但是如何查询[l,r]区间内的第k小数呢
这时候就要运用我们前缀和的思想

[l,r]的信息 = [1,r]的信息 - [1,l-1]的信息
即 S[l,r] = S[1,r] - S[1,l-1]

离散化
这个其实没什么好讲的，就是预处理，详情见代码

大概意思是懂了吧，来，让我们步入总结

常规操作
1.插入insert()，动态开点
2.查询[l,r]区间内第k小值
3.离散化

时间复杂度 O(n log^2 n)

luogu P3834
C++ 代码

 1 #include"bits/stdc++.h"
 2 
 3 using namespace std;
 4 const int N=200010;
 5 #define inl inline
 6 #define reg register
 7 #define regi register int
 8 #define PII pair<int,int>
 9 //#define ll long long
10 inl int read(void)
11 {
12     int x=0,f=1;char ch=getchar();
13     while(!isdigit(ch))  f=ch=='-'?-1:f,ch=getchar();
14     while(isdigit(ch))   x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
15     return x*f;
16 }
17 int a[N],n,m;
18 vector<int>    num;
19 struct node
20 {
21     int l,r,s;//左右儿子下标，区间中一共有多少个数
22 }tr[N*20];
23 int root[N],idx;//root[i]为第i课线段树的节点编号
24 #define id(x)    lower_bound(num.begin(),num.end(),x)-num.begin()
25 //id(x)为映射
26 int build(int l,int r)
27 {
28     int p=++idx;
29     if(l==r)    return p;
30     int mid=l+r>>1;
31     tr[p].l=build(l,mid),tr[p].r=build(mid+1,r);
32     return p;//返回当前节点的编号
33 }
34 inl int insert(int p,int l,int r,int x)
35 {
36     int q=++idx;//创建新点q
37     tr[q]=tr[p];//复制旧点p 
38     if(l==r)
39     {
40         tr[q].s++;
41         return q;
42     }
43     int mid=l+r>>1;
44     if(x<=mid)    tr[q].l=insert(tr[p].l,l,mid,x);//x出现在左子树，修改左子树
45     else    tr[q].r=insert(tr[p].r,mid+1,r,x);//x出现在右子树，修改右子树
46     tr[q].s=tr[tr[q].l].s+tr[tr[q].r].s;//统计
47     return q;//返回当前分配使用的新节点编号
48 }
49 inl int query(int q,int p,int l,int r,int k)//查询区间
50 {
51     if(l==r)    return l;
52     int s=tr[tr[q].l].s-tr[tr[p].l].s;//线段树相减
53     int mid=l+r>>1;
54     if(k<=s)    return query(tr[q].l,tr[p].l,l,mid,k);//左儿子数字大于或等于k时，说明第k小数在右子树
55     return query(tr[q].r,tr[p].r,mid+1,r,k-s);//否则在左子树
56 }
57 void init()
58 {
59     //离散化
60     sort(num.begin(),num.end());
61     num.erase(unique(num.begin(),num.end()),num.end());
62     root[0]=build(0,num.size()-1);
63     
64 }
65 int main(void)
66 {
67     n=read(),m=read();
68     for(regi i=1;i<=n;i++)
69     {
70         a[i]=read();
71         num.push_back(a[i]);
72     }
73     init();
74     for(regi i=1;i<=n;i++)    root[i]=insert(root[i-1],0,num.size()-1,id(a[i]));
75     while(m--)
76     {
77         int l=read(),r=read(),k=read();
78         printf("%d\n",num[query(root[r],root[l-1],0,num.size()-1,k)]);
79     }
80     return 0;
81 }

可持续化的思想都基本是这样的，包括可持续化平衡树，可持续化堆（注意是思想，比如可持续化堆有的时候就不能动态开点）