左偏树学习笔记

标签：log int rx 笔记学习左偏节点 dis

一、前言

左偏树是一种可以在 \(O(\log n)\) 内快速合并的堆式数据结构。
具体来说，
插入一个元素：\(O(\log n)\)。
查询最值：\(O(1)\)。
删除最值：\(O(\log n)\)。
合并：\(O(\log n)\)。
减少一个元素的值：\(O(\log n)\)。
同时它可以持久化。

二、定义

外节点：左儿子或者右儿子为空的节点。
一个节点 \(x\) 的距离 \(dis_x\) 代表节点 \(x\) 到其所在的子树内的最近的外节点的距离。特别地，如果 \(x\) 是外节点，\(dis_x=0\)；如果 \(x\) 是空节点，\(dis_x=-1\)。

三、性质

左偏树满足小/大根堆的性质，即对于所有节点 \(x\)，满足 \(v_x\le v_{lx}\) 且 \(v_x\le v_{rx}\)，或者对于所有节点 \(x\)，满足 \(v_x\ge v_{lx}\) 且 \(v_x\ge v_{rx}\)。
左偏树具有左偏性质，即对于任何一个节点 \(x\)，有 \(dis_{lx}\ge dis_{rx}\)。

四、结论

\(dis_x=dis_{rx}+1\)。这是因为根据定义，\(dis_x=min(dis_{lx},dis_{rx})+1\) 并且 \(dis_{lx}\ge dis_{rx}\)。
距离为 \(n\) 的左偏树一共至少 \(2^{n+1}-1\) 个节点，取等时它是满二叉树。这是因为根据定义，对于左偏树中的每一个节点 \(x\) 都满足 \(dis_{lx}\ge dis_{rx}=n-1\)，否则 \(dis_{lx}\le dis_{rx}\)，与性质矛盾。所以左子树的第 \(dis_{rx}+1=n\) 层的所有节点全部存在。递归地考虑，知道它至少是一棵满二叉树。所以至少 \(2^{n+1}-1\) 个节点。
一棵有 \(n\) 个节点的左偏树距离至多为 \(\lfloor log_2(n+1)\rfloor-1\)。可以由结论 2 推得。

五、实现

我们以根节点的编号指代一棵左偏树。这里我们假定维护的是小根堆，即全部求的是节点权值的最小值。

merge(x,y)：合并两个以节点 \(x\)、\(y\) 为根的左偏树，返回合并后的左偏树的根节点编号。这是左偏树最基础的操作。
1. 首先，如果两棵树中有一棵为空，那么返回另外一棵树。
2. 如果两棵树都非空，不妨假设 \(x\) 小于 \(y\)，否则交换 \(x\)，\(y\) 以避免讨论。
3. 将 \(y\) 与 \(x\) 的右子树 \(r_x\) 合并。
4. 返回时，如果回溯到节点 \(p\) 时， \(p\) 的右子节点 \(r_p\) 的距离 \(dis_{rp}\) 大于 \(p\) 的左子节点 \(l_p\) 的距离。 \(dis_{lp}\)，那么这不满足左偏树的左偏性质。所以我们交换 \(p\) 的左右子树即可。
5. 最后，由于节点 \(p\) 的距离可能发生改变，我们要更新 \(p\) 的距离，即令 \(dis_p\leftarrow dis_{rp}+1\)。
  总结：这样就可以合并两棵左偏树了。由于所有遍历过的节点都被更新了，所以这种修改后的依然是一棵左偏树。时间复杂度是原先的 \(dis_x\)，是 \(O(\log n)\) 级别的。
求最小值：根节点的值，时间复杂度 \(O(1)\)。
删除最小值：删除根节点，合并根节点的左右子树，时间复杂度与合并两棵左偏树相同，为 \(O(\log n)\)。
插入新节点：容易知道一个点也是一棵左偏树，所以可以看做两棵左偏树的合并。时间复杂度也是 \(O(\log n)\)。
左偏树的建树：将所有节点作为左偏树放进先进先出的队列里，每次拿出队首的两棵左偏树，将它们合并后放到队尾。那么前 \(\frac{n}{2}\) 次合并的是距离为 \(0\) 的左偏树，然后 \(\frac{n}{4}\) 次合并的是距离为 \(1\) 的左偏树，……，然后 \(\frac{n}{2^i}\) 次合并的是距离为 \(i-1\) 的左偏树。总复杂度为 \(\frac{n}{2}\times O(1)+\frac{n}{4}\times O(2)+\frac{n}{8}\times O(3)+……=O(n)\)。
在左偏树上删除一个指定节点（并非删除值为 \(x\) 的节点，而是删除编号为 \(x\) 的节点）。
1. 首先，我们将 \(x\) 的左子树、右子树合并，得到 \(x\) 的子树新的根节点 \(p\)。
2. 如果 \(p\) 是全局的根节点，结束操作。
3. 否则继续分类讨论，令 \(q\) 为 \(p\) 的父亲节点。
  1. 新树的距离为 \(dis_p\)，如果满足 \(dis_q=dis_p+1\) ，那么结束操作。
  2. 如果满足 \(dis_q>dis_p+1\)，那么 \(q\) 的距离应该更新为 \(dis_p+1\)，而且如果 \(p\) 是 \(q\) 的左子节点，要交换 \(q\) 的左右子树。然后继续向上更新 \(q\) 的父亲节点。
  3. 如果满足 \(dis_q<dis_p+1\)，那么 \(q\) 的距离应该更新为 \(dis_p-1\)，而且如果 \(p\) 是 \(q\) 的右子节点，要交换 \(q\) 的左右子树。然后继续向上更新 \(q\) 的父亲节点。
    总结：这样就可以删除任何一个指定节点了。合并是 \(O(\log n)\) 的，向上更新是 \(O(\log n)\) 的，总复杂度 \(O(\log n)\)。
获得节点 \(x\) 所在的左偏树的根节点。直接向上跳，使用路径压缩即可。需要维护 \(rt_x\) 的值，在合并和删除时要更新。这个操作好像是均摊的，所以也许不可以可持久化。

六、例题

例 1.P3377 【模板】左偏树（可并堆）

点击查看代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-')f=0;ch=getchar();}
	while('0'<=ch&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	return f?x:-x;
}
inline void write(int x){
	if(x<0)putchar('-'),x=-x;
	if(x>=10)write(x/10);
	putchar(x%10+48);
}
int n,m,v[100010],l[100010],r[100010],d[100010],dl[100010],rt[100010];
int merge(int x,int y){
	if(!x||!y)return x+y;
	if(v[x]>v[y]||x>y&&v[x]==v[y])swap(x,y);
	r[x]=merge(r[x],y);
	if(d[r[x]]>d[l[x]])swap(l[x],r[x]);
	d[x]=d[r[x]]+1;
	return x;
}
int find(int x){
	return x==rt[x]?x:rt[x]=find(rt[x]);
}
int main(){
	n=read();m=read();d[0]=-1;
	for(int i=1;i<=n;i++)v[i]=read(),rt[i]=i;
	for(int op,x,y;m;m--){
		op=read();x=read();
		if(op==1){
			y=read();
			if(dl[x]||dl[y])continue;
			x=find(x);y=find(y);
			if(x!=y)rt[x]=rt[y]=merge(x,y);
		}else{
			if(dl[x]){puts("-1");continue;}
			x=find(x);
			write(v[x]);putchar(10);
			rt[x]=rt[l[x]]=rt[r[x]]=merge(l[x],r[x]);
			dl[x]=1;d[x]=l[x]=r[x]=0;
		}
	}
	return 0;
}