主席树的简要讲解
区间第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 }
可持续化的思想都基本是这样的，包括可持续化平衡树，可持续化堆（注意是思想，比如可持续化堆有的时候就不能动态开点）