左偏树学习笔记 | juju527's blog

左偏树

左偏树是一种二叉的可并堆，故名思意，左偏树左边的节点多于右边节点

对于堆中的每一个节点，维护一个 $d$ 值，定义为其往子树走最少多少步走到空节点

我们希望维护出来的堆一直往右走就能最快走到空

左偏树最核心的操作是“合并”

考虑合并两个大小分别为 $n,m$ 的堆 $x,y$

取出一个更优的点，不妨是 $x$ ,将 $x$ 的右儿子和 $y$ 递归合并

由于合并时一直在往右走，复杂度 $O(logn+logm)$

插入操作可视为堆与一个单独节点合并，删除堆顶可视为将堆顶左右儿子合并

值得一提的是，左偏树支持打懒标记（全体加/乘）

左偏树支持可持久化，类似线段树合并，合并过程不断新建节点即可

若最初总共有 $n$ 个节点，考虑合并两个大小分别为 $s_1,s_2$ 的左偏树

其遍历节点数至多为 $logs_1+logs_2$ ，最多合并 $n$ 次，时空复杂度 $O(nlogn)$

求s到t的第k短路

考虑先跑出反图上t点的最短路树 $T$ ，复杂度 $O(mlogm)$

考虑一条s到t的路径边集 $P$ ，记去除 $T$ 上的边后的边集为 $P'$

$P'$ 中相邻的两条边 $e_1,e_2$ 一定满足 $e_2$ 的起点在 $e_1$ 终点到 $t$ 的链上

显然，不同的 $P'$ 对应了不同的 $P$ ，我们考虑维护 $P'$ 即可

对于已有的一个 $P'$ ，我们通过增加新边/替换最后一条边得到权值略大的集合 $P''$

增加新边相当于我们要找到最小的一条以 $P'$ 中最后一条边的终点到 $t$ 的链上的一个点为起点的非树边

替换边相当于我们要找到次小的一条以 $P'$ 中倒数第二条边的终点到 $t$ 的链上的一个点为起点的非树边

我们考虑维护堆 $H(x)$ ，储存点 $x$ 到 $t$ 的链上的点为起点的非树边

显然我们不能暴力维护它，复杂度将达到 $O(nmlogm)$

发现 $H(x)$ 和 $H(fa_x)$ 有大量重合，我们维护一个可持久化堆即可，复杂度 $O(mlogm)$

显然，上面提到的操作当我们维护出 $H(x)$ 就已经迎刃而解了

总复杂度 $O(nlogn+mlogm+klogk)$

通过斐波那契堆优化最短路+维护堆套堆可以做到 $O(nlogn+m+klogk)$