线段树进阶——权值线段树与动态开点前置知识：线段树权值线段树我们都知道，普通的线段树是⼀种⽤来维护序列区间最值的⼀种数据结构。
⽽权值线段树，就是将序列中各个值出现的频数作为权值，再⽤线段树来维护值域的数据结构。
与其说是⼀种数据结构，更不如说是⼀个线段树的 trick。
实际代码的话，⽤线段树维护桶数组就⾏了。
权值线段树重要作⽤是反应序列中元素的⼤⼩问题，如求第k⼤第k⼩问题。
因为本⾝就与普通线段树差不多，所以就直接放模板了((code:#include <bits/stdc++.h>using namespace std;const int N=3e5+10;int n,k_;int bucket_[N];int tree[N<<1];void push_up(int node){tree[node]=tree[node<<1]+tree[node<<1|1];}void build(int node,int start,int end){if(start==end){tree[node]=bucket_[start];return ;}int mid=start+end>>1;int lnode=node<<1;int rnode=node<<1|1;build(lnode,start,mid);build(rnode,mid+1,end);push_up(node);}void update(int node,int start,int end,int k,int val)//⼤⼩为val的数多k个,相当于单点修改{if(start==end){tree[node]+=k;return ;}int mid=start+end>>1;int lnode=node<<1;int rnode=node<<1|1;if(val<=mid) update(lnode,start,mid,k,val);else update(rnode,mid+1,end,k,val);push_up(node);}int query(int node,int start,int end,int val)//查询数字val有多少个，相当于单点查询{if(start==end) return tree[node];int mid=start+end>>1;int lnode=node<<1;int rnode=node<<1|1;if(val<=mid) return query(lnode,start,mid,val);else return query(rnode,mid+1,end,val);push_up(node);}int query_kth(int node,int start,int end,int k)//查询第k⼩{if(start==end) return start;int mid=start+end>>1;int lnode=node<<1;int rnode=node<<1|1;if(tree[lnode]>=k) return query_kth(lnode,start,mid,k);//如果左⼦树的权值⼤于k，证明第k⼩值左⼦树else return query_kth(rnode,mid+1,end,k-tree[lnode]);//进⼊右⼦树时，整个区间的第k⼩相当于右区间的第(k-左区间)⼩，记得减去左⼦树的值}Processing math: 100%if(start==end) return start;int mid=start+end>>1;int lnode=node<<1;int rnode=node<<1|1;if(tree[rnode]>=k) return query_kthbig(rnode,mid+1,end,k);//若右⼦树的权值⼤于k，证明第k⼤值在右⼦树else return query_kthbig(lnode,start,mid,k-tree[rnode]);//进⼊左⼦树时，记得减去右区间}int main(){scanf("%d%d",&n,&k_);int maxn=0,tot=0;for(int i=1; i<=n; i++){int x;scanf("%d",&x);maxn=maxn>=x?maxn:x;bucket_[x]++;}build(1,1,maxn);cout<<query_kth(1,1,maxn,k_);return 0;}板⼦题：由于重复的不算，⽤桶统计出现次数的时候只统计到1就⾏了。
