主席树（结构体实现，代码简单）

妖狐艹你老母 2022-02-19 06:29 140阅读 0赞

### 今天又学习主席树，看网上的博客，大佬们思路很清晰，看到代码的时候，惊了~ ###

### 什么和什么啊 ，l数组，r数组，rot数组，，遍地开花，于是自己手动了一个结构体主席树   代码还凑合   ###

### 先看别人家的思路，看完思路再来我这里看全网最简单易懂代码~哈哈哈哈 ###

思路博客：[https://www.cnblogs.com/zyf0163/p/4749042.html][https_www.cnblogs.com_zyf0163_p_4749042.html]

代码是模板题  给一个数组 求区间第K大[http://acm.hdu.edu.cn/showproblem.php?pid=2665][http_acm.hdu.edu.cn_showproblem.php_pid_2665]

#include<bits/stdc++.h>
    using namespace std;
    struct Node{int l,r,sum;} t[4000000];
    int a[100001],b[100001],root[100001],n,m,T,sz,cnt,ll,rr,w;
    void build(int & o,int l,int r){//建立一个空树,从建树的过程来看，数据范围一定要确定，卧槽(这数据结构太傻了) 
    	o=++cnt;
    	t[o].sum=0;//这个树的个数为0
    	if(l==r) return ;
    	int mid=(l+r)>>1;
    	build(t[o].l,l,mid);//和线段树不同的是，左右的根不再是区间的左右边界了，
    	build(t[o].r,mid+1,r);//而是指向的不同的根。也就是第一个是总根  t[2]是总根的左子树的根 t[3] 是右子树的根 
    }
    void update(int &o,int l,int r,int last,int v){
    	o=++cnt;//开辟新的根节点
    	t[o].l=t[last].l;
    	t[o].r=t[last].r;
    	t[o].sum=t[last].sum+1;
    	if(l==r)return ;
    	int mid=(l+r)>>1;
    	if(v<=mid) update(t[o].l,l,mid,t[last].l,v);//对左边 
    	else update(t[o].r,mid+1,r,t[last].r,v);
    } 
    int ask(int pre,int now,int l,int r,int k){
    	if(l==r)return l;
    	int mid=(l+r)>>1,num=t[ t[now].l ].sum-t [ t[pre].l ].sum;
    	if(k<=num)return ask(t[ pre ].l,t[now].l,l,mid,k);
    	else return ask(t[pre].r,t[now].r,mid+1,r,k-num); 
    }
    int main(){
    	scanf("%d",&T);
    	while(T--){
    		cnt=0;
    		scanf("%d%d",&n,&m);
    		for(int i=1;i<=n;i++){
    			scanf("%d",&a[i]);
    			b[i]=a[i];
    		}
    		sort(b+1,b+n+1);
    		sz=unique(b+1,b+n+1)-(b+1);//数据个数 
    		
    		//cout<<sz<<endl;
    		//for(int i=1;i<=n;i++)cout<<b[i]<<" ";cout<<endl;
    		
    		for(int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+sz+1,a[i])-b;
    		build(root[0],1,sz);//对数据范围进行建一颗空树
    
    		//for(int i=0;i<=4*n;i++)printf("%d,rt =  %d,ls =  %d, rs = %d, sum = %d\n",i,root[i],t[i].l,t[i].r,t[i].sum);
    
    		for(int i=1;i<=n;i++)update(root[i],1,sz,root[i-1],a[i]);//线段树插入over 
    
    		//for(int i=0;i<=5*n;i++)printf("%d,rt =  %d,ls =  %d, rs = %d, sum = %d\n",i,root[i],t[i].l,t[i].r,t[i].sum);
    
    		while(m--){
    			scanf("%d%d%d",&ll,&rr,&w);
    			printf("%d\n",b[ask(root[ll-1],root[rr],1,sz,w)]);//为什么调10几分钟bug？？因为离散化要离散回来 
    		}
    	}
    	return 0;
    }

一发AC~  哈哈哈

[https_www.cnblogs.com_zyf0163_p_4749042.html]: https://www.cnblogs.com/zyf0163/p/4749042.html
[http_acm.hdu.edu.cn_showproblem.php_pid_2665]: http://acm.hdu.edu.cn/showproblem.php?pid=2665