权值线段树与主席树（初步）

1.首先,给你一颗值为横坐标的线段树,每个节点上存着该值出现了多少次,这样的一颗线段树你会求区间k大值吧.二分即可.

2.然后,假设区间是数组arr[n],区间长度是n,那么给你n颗线段树,第i颗线段树是第i-1颗线段树插入arr[i]得到.

3.如果你有了这n颗线段树,想求区间[l,r]中的第k大值,那么你需要在第r颗和第l-1颗线段树的差线段树上作二分,可以求得区间第k大值.

4.差线段树很好理解,比如你有一个部分和数组sum,sum[r]-sum[l-1]就是部分和的差,代表区间[l,r]的和,差线段树同理.

5.还有一个问题需要解决，那就是空间问题。显而易见的是，如果每输入一个数就重新构造一棵权值线段树，必然会导致空间不够用：一棵线段树的空间就是n*4，那么一共的空间开销就是n*n*4，显然是会MLE的。那么这个问题怎么解决呢？可以发现每更新一个点，就会从它开始把它的所有祖先都更新一次，而其他的点都没有被改变，即：每次改变的结点只有logn个。这样，我们每次输入一个数，只需要多开logn个空间，那么实际的空间开销只有n*(4+logn)，满足了空间要求。
 

可持久化线段树的核心思想是既然变化很小就只记录变化(用数组模拟链表，串其各个时期的线段树).
用它求区间k大值的核心思想是部分和思想,也就是差线段树（或者可以说是通过线段树使两个前缀和做差）

来自 知乎Comzyh

额我向来是电科大的粉丝，附上卿学姐的B站视频和卿学姐的代码

其实可以把主席树想象成一颗链树，在链树上的二分查找，就有点像链表那样，通过链表的方式实现不同时期的主席树之间的差值查询。

总之这种数据结构题在区域赛上是为了争银屁屁用的，有点难，Mandy.H.Y和殇雪还有Stupid_Turtle这三位大佬写得很nice。

并附上poj 2104 简单的求区间第K大个数的代码。

#include<iostream>
#include<algorithm>
#include<vector>
#include<string.h>
using namespace std;
typedef long long ll; 
const int maxn=0x3f3f3f3f;
const int ans=1e5+7;
int n,m,cnt,root[ans],a[ans],x,y,k;
struct node{
    int l;
	int r;
	int sum;
}T[ans*40];
vector<int>v;
int getid(int x){return lower_bound(v.begin(),v.end(),x)-v.begin()+1;}
void update(int l,int r,int &x,int y,int pos){
	T[++cnt]=T[y],T[cnt].sum++,x=cnt;
    if(l==r) return;
    int mid=(l+r)/2;
    if(mid>=pos) update(l,mid,T[x].l,T[y].l,pos);
    else update(mid+1,r,T[x].r,T[y].r,pos);
}
int query(int l,int r,int x,int y,int k){
    if(l==r) return l;
    int mid=(l+r)/2;
    int sum=T[T[y].l].sum-T[T[x].l].sum;
    if(sum>=k) return query(l,mid,T[x].l,T[y].l,k);
    else return query(mid+1,r,T[x].r,T[y].r,k-sum);
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]),v.push_back(a[i]);
	
	sort(v.begin(),v.end());//离散化 
    v.erase(unique(v.begin(),v.end()),v.end());
    
    //离线处理 
    for(int i=1;i<=n;i++) update(1,n,root[i],root[i-1],getid(a[i])); 
    
    //离线处理后查询 
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&x,&y,&k);
        printf("%d\n",v[query(1,n,root[x-1],root[y],k)-1]);
    }
    return 0; 
}