定义:主席树是一种可持久化的线段树 又叫函数式线段树
刚开始学是不是觉得很蒙逼啊 其实我也是
主席树说简单了 就是保留你每一步操作完成之后的线段树 然后有可加减性
呃 。。。 这么说好像还是有点生涩
那么就拿poj2104来举例子吧 慢慢讲我觉得会很好的
题意就是给你一个100000长度的数字 然后100000次询问[L,R]之间第k大的数字是多少
这个很容易看出来 暴力根本不可以 黑你分分钟的事情啊
我们怎么办呢 想想线段树能不能做 想来想去 一颗线段树好像不能这么做 GG
那么我们做一个美好的假设:
我们建立100000棵美丽的线段树 每一个线段树的节点 表示这一个区间内有多少个数字
第一棵线段树保存着把第一个数字插入进去之后 每个区间有多少个数字
第二棵线段树保存着把第一个 第二个数字插入进去之后 每个区间有多少个数字
。
。
。
。
第n棵线段树保存着把第1,2,3。。。。n个数字插入进去之后 每个区间有多少个数字
好了 我们已经建立了这么多的线段树 我们接下来该怎么办呢?
对 就是查询
可是如何查询呢? 假设我们要查询[l,r]内的第k大
我们可以拿出第l-1 ,r 棵线段树,然后两者相减 我们想一下 这样不就得到了相当于插入了第l到r个点所建立的一棵线段树 这棵线段树每个节点保留的信息是:这个区间内数字的个数 然后我们往下二分查找 就可以得到第k大了
现在的问题时 这么庞大的空间开销我们耗费不起 我们该如何建立这样的线段树呢?
答案就是 我们要尽量利用重复节点
我们可以想一下 我们每次建立线段树 相对于前一棵线段树 我们只修改了它的一条路径 最多只有logn的变化 那么我们就存下这logn的变化 尽可能的利用重复节点 就可以达到重复使用的目的 有张图你们自己体会一下 我也是盗图 侵删~
每次只修改一条路径
这样就能完成我们的主席树了
接下来是我自己写的该题代码
#include <iostream>#include <algorithm>#include <stdio.h>#include <string.h>#include <stdlib.h>using namespace std;#define maxn (int)(1e6+10)struct node{ int cnt,l,r;}treenode[30*maxn];//定义一个结构体吧 要不心累 l 和 r 表示 左右两个节点的序号 这个不是单纯的单个线段树了 这个还是有必要的 最好开20-40倍int tree_cnt[maxn];//每个线段树跟节点的坐标 这个是搜索的起点啊int init[maxn];//int cop[maxn];int n,t_cnt=0,newn;//t_cnt是现在数组开到多大了 然后建立下一个的时候注意++t_cnt;int getid(int x) {return (int)(lower_bound(init,init+newn,x)-init);}//数据太大 需要离散化int insert(int num,int becopyed,int l,int r)//记住返回自己的坐标{ ++t_cnt; treenode[t_cnt].cnt=treenode[becopyed].cnt+1; int save=t_cnt; int mid=(l+r)/2; if(l==r) { return save; } else if(num<=mid) { treenode[save].l=insert(num,treenode[becopyed].l,l,mid); treenode[save].r=treenode[becopyed].r; } else { treenode[save].r=insert(num,treenode[becopyed].r,mid+1,r); treenode[save].l=treenode[becopyed].l; } return save;}int query(int x,int y,int k,int l,int r){ if(l==r) return l; int p=(treenode[treenode[y].l].cnt-treenode[treenode[x].l].cnt); int mid=(l+r)/2; if(k<=p) { return query(treenode[x].l,treenode[y].l,k,l,mid); } else return query(treenode[x].r,treenode[y].r,k-p,mid+1,r);}//一边做减法 一边查询void PRint(int x,int l,int r){ cout<<treenode[x].cnt<<' '; if(l==r) {return;} int mid=(l+r)>>1; print(treenode[x].l,l,mid); print(treenode[x].r,mid+1,r);}int main(){ int n,qnum; cin>>n>>qnum; for(int i=0;i<n;++i) {scanf("%d",init+i);cop[i]=init[i];} sort(init,init+n); newn=unique(init,init+n)-init; for(int i=1;i<=n;++i) { int p=insert(getid(cop[i-1]),tree_cnt[i-1],0,n); tree_cnt[i]=p; //cout<<p<<endl; } for(int i=0;i<qnum;++i) { int x,y,k; scanf("%d %d %d",&x,&y,&k); //cin>>x>>y>>k; int ans=query(tree_cnt[x-1],tree_cnt[y],k,0,n); //cout<<ans<<endl; printf("%d/n",init[ans]); //cout<<init[ans]<<endl; } //cout<<endl; //for(int i=0;i<=n;++i) print(tree_cnt[i],0,n),cout<<endl; return 0;}
新闻热点
疑难解答