左偏树简单知识

# 左偏树

左偏树是堆的一种，具有堆的性质，同时支持快速合并，所以也被称为可并堆。先来看一些定义：
我们把一个左子树或右子树为空的节点叫做外节点。定义一个节点的 $\;dist$ 为该节点到子树中最近的外节点的距离加 $1$ ，特殊地，外节点的 $\;dist\;$ 为 $1$ ，空节点的 $\;dist\;$ 默认为 $0$ 。
注意：一个节点的 $\;dist\;$ 不是深度
然后我们看一下左偏树，它满足每个节点的左儿子的 $\;dist\;$ 大于等于右儿子的 $\;dist\;$ 。所以左偏树满足两个性质：堆的性质以及左偏性。
那我们又可以得到一个新的结论，既然它满足左偏性，那么对于一个节点的 $\;dist\;$ ，是由其右儿子的 $\;dist\;$ 决定的，所以我们得到如下式子：
$tr[x].dist = tr[tr[x].r].dist+1$

左偏树的核心操作就是合并。那我们以小根堆为例，假设我们现在有堆 $x$ 和堆 $y$ ，我们要让值较小的那个成为新堆的根，然后递归合并其右儿子和另一个堆即可。由于需要满足左偏性质，如果合并后左儿子的 $\;dist\;$ 小于右儿子的 $\;dist\;$ ，交换左右儿子。
合并代码如下：

	int merge(int x,int y)// 返回合并后的堆顶
	{
	if(x==0 \|\| y==0) return x+y;// 有一个堆是空的
	if(tr[x].v<tr[y].v) swap(x,y);
	tr[x].r=merge(tr[x].r,y);
	if(tr[tr[x].r].dis>tr[tr[x].l].dis) swap(tr[x].l,tr[x].r);
	tr[x].dis=tr[tr[x].r].dis+1;
	return x;
	}

合并操作复杂度为 $O(\log n+\log m)$ ，其中 $n\;m$ 分别为两个堆的大小。

然后是一些拓展应用
插入节点
将节点看成一个堆，直接合并即可
删除堆顶元素
考虑直接合并堆顶的左儿子和右儿子，就相当于把堆顶删掉了
在每个节点上也可以维护一些信息和懒标记

# 题目练习

【模板】左偏树（可并堆）

左偏树模板题，我们对每个节点 $i$ 维护一个其所在的堆的堆顶元素 $fa[i]$ ，运用类似并查集状态压缩的技巧去查找堆顶元素。对于合并堆 $\,x\,$ 和 $\,y\,$ ，我们需要更新 $fa$ 数组 $\,fa[x]=fa[y]=merge(x,y)$

Monkey King
与上一道题类似，对于将一个节点 $\,p\,$ 的 $\;val\;$ 减少一半这个操作，我们先将节点 $\,p\,$ 的左儿子和右儿子合并，删除原来的节点 $\,p\,$ ，得到一个新的根 $\,root\,$ ，再将 $\,root\,$ 和 $\,p\,$ 再次合并就能将 $\,p\,$ 重新插入回去。