可持久化可并堆
可持久化可并堆一般用于求解 k 短路问题。
如果一种可并堆的时间复杂度不是均摊的,那么它在可持久化后单次操作的时间复杂度就保证是 O(\log n) 的,即不会因为特殊数据而使复杂度退化。
可持久化左偏树¶
在学习本内容前,请先了解 左偏树 的相关内容。
回顾左偏树的合并过程,假设我们要合并分别以 x,y 为根节点的两棵左偏树,且维护的左偏树满足小根堆的性质:
-
如果 x,y 中有结点为空,返回 x+y。
-
选择 x,y 两结点中权值更小的结点,作为合并后左偏树的根。
-
递归合并 x 的右子树与 y,将合并后的根节点作为 x 的右儿子。
-
维护当前合并后左偏树的左偏性质,维护
dist
值,返回选择的根节点。
由于每次递归都会使 dist[x]+dist[y]
减少一,而 dist[x]
是 O(\log n) 的,一次最多只会修改 O(\log n) 个结点,所以这样做的时间复杂度是 O(\log n) 的。
可持久化要求保留历史信息,使得之后能够访问之前的版本。要将左偏树可持久化,就要将其沿途修改的路径复制一遍。
所以可持久化左偏树的合并过程是这样的:
-
如果 x,y 中有结点为空,返回 x+y。
-
选择 x,y 两结点中权值更小的结点,新建该结点的一个复制 p,作为合并后左偏树的根。
-
递归合并 p 的右子树与 y,将合并后的根节点作为 p 的右儿子。
-
维护以 p 为根的左偏树的左偏性质,维护其
dist
值,返回 p。
由于左偏树一次最多只会修改并新建 O(\log n) 个结点,设操作次数为 m,则可持久化左偏树的时间复杂度和空间复杂度均为 O(m\log n)。
参考实现¶
1 2 3 4 5 6 7 8 9 10 11 |
|
build本页面最近更新:,更新历史
edit发现错误?想一起完善? 在 GitHub 上编辑此页!
people本页面贡献者:OI-wiki
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用