学习笔记第七节:主席树
正题
主席树看上去很高级(President Tree),毕竟说的是习大大。
但是其实理念挺low的,在百度上一查,发现,艾~这不是函数式线段树吗~
那么说明主席树跟线段树是有着密不可分的联系的。
说白了,我们要学习的就是,如何优化线段树的时间来换更少的空间。
前面都是废话
我们可以用这题来引入。
要你求静态区间第k大。
怎么求呢?
我们有些同学搞笑说,nm过一下加一加莫队优化emm。
过可能是过的了,但是掌握不了主席树后面的习题怎么办??
现在开始说。
1.首先我们肯定想着怎么求第k大,想着想着,就发现线段树是一个不错的东西。
2.我们用n棵线段树来维护,第i棵线段树表示的是1~i的信息,根节点维护权值为[l,r]区间的信息。
3.信息包括(左儿子,右儿子,这个点所管理区间内的数的个数)
4.这样就能够满足n棵线段树维护区间(求区间,前缀和相减即可),而左右儿子来满足二分查找。
5.好像是这么吧~
听不懂吧~
比如说当前区间是1,5,2,3,4.
那么你会建出n棵线段树如下
分别对应着[1],[1,5],[1,5,2],[1,5,2,3],[1,5,2,3,4];
那么我们要处理区间的时候,就把第r棵和第l-1棵提出来,让他们相减,在找到所需位置即可。
然后就跑,结果发现空间超限了。
emm,又发现,时间超限了emmmm。
其实你有没有发现,我们建出来的前缀树和它的前一个很相似。
甚至我们发现,对于前一个来说,当前的变动只有一条链(也就是log2(n))那么多而已。
所以我们就想着,假如我们要修改左儿子,能不能把右儿子连向上一个的右儿子?
而左儿子独立更新?
当然是可以的。可以看代码理解一下。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,m;
int fact[200010];
struct node{
int x,d;
bool operator<(const node q)const{
return d<q.d;
}
}p[200010];
int a[200010];
struct tree{
int ls,rs,tot,x,y;
}s[6400010];
int root[200010];
int len=0;
void build(int x,int y){//以前比较傻,第一棵树全建,后面您就会知道为什么不用了,因为第一棵树相对于没有点的树,变动也是logn
len++;
int i=len;
s[i].ls=s[i].rs=-1;
s[i].tot=0;
s[i].x=x;s[i].y=y;
if(x<=a[1] && a[1]<=y) s[i].tot=1;
if(x==y) return ;
int mid=(x+y)/2;
s[i].ls=len+1;build(x,mid);
s[i].rs=len+1;build(mid+1,y);
}
void go(int x){//往下更新。
int now=root[x-1];
while(1){
len++;//当前点要建
s[len]=s[now];//大部分和上一棵树相同
s[len].tot++;//其中的tot要加一
if(s[now].x==s[now].y) return ;//叶子结点就退出
if(a[x]<=s[s[now].ls].y) {s[len].ls=len+1;now=s[now].ls;}//看是在左还是在右,在左就把左儿子更新,否则就不动。
else {s[len].rs=len+1;now=s[now].rs;}//否则把右儿子更新。
}
}
int solve(int x,int y,int c){
int now=root[x],op=root[y];
while(s[op].x!=s[op].y){//两棵线段树往下跑
int u=s[s[op].ls].tot-s[s[now].ls].tot;//看一下左边有多少个
if(c<=u) {op=s[op].ls;now=s[now].ls;}//在左边就去
else {op=s[op].rs;now=s[now].rs;c-=u;}//在右边就去
}
return s[op].x;
}
int main(){
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&p[i].d),p[i].x=i;
sort(p+1,p+1+n);
int t=0;
for(int i=1;i<=n;i++) a[p[i].x]=++t,fact[t]=p[i].d;
build(1,n);
root[1]=1;
for(int i=2;i<=n;i++){
root[i]=len+1;
go(i);
}
for(int i=1;i<=m;i++){
int x,y,c;
scanf("%d %d %d",&x,&y,&c);
if(y<x) swap(y,x);
printf("%d\n",fact[solve(x-1,y,c)]);
}
}
其实上面的代码很冗长,只是方便读者理解罢了。
后面会写成恶心但简短的递归形式,并且会教读者动态第k大,用主席树来维护路径第k大和子树第k大(树链剖分和dfs序)。当然还有差分+主席树,该回宿舍睡觉了要不就会被阿姨抓emm,其实我的答复会更有趣无聊欢迎提问。
上一篇: 使用小觅相机录制数据集