【瞎口胡】左偏树

本篇内容将持续更新。

左偏树是一种支持 \(O(\log n)\) 合并的堆。

dist 相关

要了解左偏树,首先需要补充一个定义。定义二叉树中一个节点的 \(\operatorname{dist}\) 为其子树中最近的没有左儿子或右儿子的节点(称为「外节点」)到它的距离。根据定义,一个外节点的 \(\operatorname{dist}\) 为 \(0\),其余节点的 \(\operatorname{dist}\) 为其左儿子和右儿子中,较小的 \(\operatorname{dist}\) 加上 \(1\)。

同时,一棵根的 \(\operatorname{dist}\) 为 \(x\) 的二叉树的节点数量不小于 \(2^{x}-1\) 个。容易观察到,这样的二叉树至少有 \(x-1\) 层是满的,这 \(x-1\) 层的节点数量共 \(\sum \limits_{i=0}^{x-1} 2^i = 2^{x}-1\) 个。于是,我们得到了一个重要的结论:一个节点数量为 \(n\) 的二叉树的 \(\operatorname{dist}\) 是 \(O(\log n)\) 级别的。

左偏树的定义和性质

左偏树满足堆的性质。除此之外,对于任意非外节点,其左儿子的 \(\operatorname{dist}\) 不小于右儿子的 \(\operatorname{dist}\)。我们可以得到一个推论:从任意一个非外节点的左偏树节点往右儿子方向走,\(\operatorname{dist}\) 一定会减小 \(1\),至多走 \(\log\) 次就会到达外节点。

需要注意的是,一条向左的链也是一棵左偏树,因此 \(\operatorname{dist}\) 并不和深度相关。

左偏树的合并

对于两棵左偏树(以小根堆举例),在合并时会选取根的权值较小的那棵树 \(x\) 作为合并后的根,并把另外一棵树 \(y\) 和 \(x\) 的右儿子合并。

根据上一节中的推论,大小为 \(n,m\) 的两棵左偏树合并 \(O(\log n + \log m)\) 次就会出现空节点,此时停止合并即可。

struct Node{
	int son[2];
	int val;
	int dist;
}tree[N*2];
inline int& lc(int x){
	return tree[x].son[0];
}
inline int& rc(int x){
	return tree[x].son[1];
}
inline void update(int x){
	tree[x].dist=tree[rc(x)].dist+1;
	return;
}
int merge(int x,int y){
	if(!x||!y){
		return x|y;
	}
	if(tree[x].val<tree[y].val){ // 选择 val更小的作为根
		std::swap(x,y);
	}
	rc(x)=merge(rc(x),y);
	if(tree[lc(x)].dist<tree[rc(x)].dist){ // 更新右儿子维护左偏树的性质
		std::swap(lc(x),rc(x));
	}
	update(x); // 更新 dist
	return x;
}

左偏树的插入 / 删除

对于插入,就是新建一个单个节点的堆,然后合并。

对于删除则略为复杂。首先需要明确,左偏树只能够在复杂度正确的情况下删除根节点。新设一个数组 \(f\),其中 \(f_i\) 表示 \(i\) 所属左偏树的根节点。容易发现,\(f\) 就是一个并查集。在删除的时候,把当前根 \(rt\) 的左儿子 \(lc\) 和右儿子的 \(rc\) 合并在一起,并且更新 \(f_{lc}\) 和 \(f_{rc}\)。由于路径压缩的存在,可能有部分节点的 \(f\) 值仍然为 \(rt\),因此我们要把 \(f_{rc}\) 设为合并之后新根的编号,这些节点经过一次 find() 之后就能找到正确的根节点。

给出删除的代码:

inline void Delete(int x){
	f[son[x][0]]=f[son[x][1]]=f[x]=merge(son[x][0],son[x][1]);
	son[x][0]=son[x][1]=dist[x]=0; // 清空节点信息
	return;
}

例题 1 Luogu P3377【模板】左偏树(可并堆)

题意

给定 \(n\) 个小根堆,每个小根堆中有且仅有一个数。支持 \(m\) 次操作,每次操作为以下类型:

  • 合并两个堆。
  • 删除某个堆的根节点,并输出该根节点的权值。

\(1 \leq n,m \leq 10^5\)

题解

模板题。

# include <bits/stdc++.h>
# define rr register
const int N=100010;
int v[N];
int son[N][2];
int f[N];
int dist[N];
bool is[N];
int n,m;
int find(int x){
	if(f[x]==x){
		return x;
	}
	return f[x]=find(f[x]);
}
inline int read(void){
	int res,f=1;
	char c;
	while((c=getchar())<'0'||c>'9')
		if(c=='-')f=-1;
	res=c-48;
	while((c=getchar())>='0'&&c<='9')
		res=res*10+c-48;
	return res*f;		
}
int merge(int x,int y){
	if(!x||!y) 
		return x|y;
	if(v[x]>v[y]||(v[x]==v[y]&&x>y))
		std::swap(x,y);
	son[x][1]=merge(son[x][1],y);
	if(dist[son[x][1]]>dist[son[x][0]]){
		std::swap(son[x][1],son[x][0]);
	}
	dist[x]=dist[son[x][1]]+1;
	return x;
}
inline void Get(int x){
	is[x]=true;
	printf("%d\n",v[x]);
	f[son[x][0]]=f[son[x][1]]=f[x]=merge(son[x][0],son[x][1]);
	son[x][0]=son[x][1]=dist[x]=0;
	return;
}
int main(void){
	n=read(),m=read();
	for(rr int i=1;i<=n;++i){
		v[i]=read(),f[i]=i;
	}
	int opt,x,y;
	while(m--){
		opt=read(),x=read();
		if(opt==1){
			y=read();
			if(is[x]||is[y]){
				continue;
			}
			x=find(x),y=find(y);			
			if(x==y){
				continue;
			}
			f[x]=f[y]=merge(x,y);
		}else{
			if(is[x]){
				puts("-1");
				continue;
			}
			Get(find(x));
		}
	}
	return 0;
} 

例题 2 Luogu P1456 Monkey King

题意

有 \(n\) 只猴子和 \(m\) 次冲突。每只猴子有一个强壮值,第 \(i\) 只猴子的强壮值为 \(s_i\)。每次冲突包括两只猴子 \(x,y\)。

  • 如果 \(x\) 和 \(y\) 认识,那么什么都不会发生。此时请输出 \(-1\)。
  • 如果 \(x\) 和 \(y\) 不认识,那么他们会分别邀请各自最强壮的朋友进行决斗。决斗之后,参加决斗的两位强壮值减半(下取整),\(x\) 和 \(y\) 以及各自的朋友会互相认识。此时请输出决斗之后他们最强壮的朋友的强壮值。

\(1 \leq n,m \leq 10^5\),多组数据

题解

决斗操作本质是先删除,修改点权,再插入。

明白这一点就可以直接做了。

# include <bits/stdc++.h>

const int N=100010,INF=0x3f3f3f3f;

struct Node{
	int son[2];
	int val;
	int dist;
}tree[N*2];
int f[N*2],cnt;
int n,m;
int root;
inline int read(void){
	int res,f=1;
	char c;
	while((c=getchar())<'0'||c>'9')
		if(c=='-')f=-1;
	res=c-48;
	while((c=getchar())>='0'&&c<='9')
		res=res*10+c-48;
	return res*f;
}
inline int& lc(int x){
	return tree[x].son[0];
}
inline int& rc(int x){
	return tree[x].son[1];
}
inline void update(int x){
	tree[x].dist=tree[rc(x)].dist+1;
	return;
}
int merge(int x,int y){
	if(!x||!y){
		return x|y;
	}
	if(tree[x].val<tree[y].val){
		std::swap(x,y);
	}
	rc(x)=merge(rc(x),y);
	if(tree[lc(x)].dist<tree[rc(x)].dist){
		std::swap(lc(x),rc(x));
	}
	update(x);
	return x;
}
inline void NewNode(int &x,int val){
	x=++cnt;
	tree[x].val=val,tree[x].dist=0,lc(x)=rc(x)=0,f[x]=x;
	return;
}
inline int find(int x){
	return (f[x]==x)?x:(f[x]=find(f[x]));
}
inline void Delete(int x){
	f[x]=f[lc(x)]=f[rc(x)]=merge(lc(x),rc(x));
	tree[x].dist=0;
	return;
}
int main(void){
	while(~scanf("%d",&n)){
		cnt=root=0;
		for(int i=1;i<=n;++i){
			int x,val=read();
			NewNode(x,val);
		}
		m=read();
		while(m--){
			int u=read(),v=read();
			int fu=find(u),fv=find(v);
			if(fu==fv){
				puts("-1");
				continue;
			}
			int urt,vrt,Urt,Vrt;
			urt=f[lc(fu)]=f[rc(fu)]=merge(lc(fu),rc(fu)),vrt=f[lc(fv)]=f[rc(fv)]=merge(lc(fv),rc(fv));
			lc(fu)=rc(fu)=0,tree[fu].dist=0,lc(fv)=rc(fv)=0,tree[fv].dist=0;
			tree[fu].val>>=1,tree[fv].val>>=1;
			Urt=f[urt]=f[fu]=merge(urt,fu),Vrt=f[vrt]=f[fv]=merge(vrt,fv);
			f[Urt]=f[Vrt]=merge(Urt,Vrt);
			printf("%d\n",tree[f[Urt]].val);
		}
	}
	return 0;
}

更多

Luogu P2713 罗马游戏

上一篇:堆-模板


下一篇:【笔记】Go的面向对象