WIKIOI
wiki(I:)
比赛相关
工具软件
语言基础
算法基础
搜索
动态规划
字符串
数学
数据结构
图论
计算几何
杂项
专题
数据结构部分简介
栈
队列
链表
哈希表
并查集
堆简介
二叉堆
配对堆
左偏树
分块思想
块状数组
块状链表
树分块
Sqrt Tree
单调栈
单调队列
ST 表
树状数组
线段树
李超线段树
区间最值操作 & 区间历史最值
划分树
二叉搜索树简介
Treap
Splay
WBLT
Size Balanced Tree
AVL 树
替罪羊树
笛卡尔树
左偏红黑树
跳表
可持久化数据结构简介
可持久化线段树
可持久化块状数组
可持久化平衡树
可持久化字典树
可持久化可并堆
线段树套线段树
平衡树套线段树
线段树套平衡树
树状数组套主席树
分块套树状数组
K-D Tree
珂朵莉树
Link Cut Tree
Euler Tour Tree
Top Tree
析合树
50 objects
本站非官方,所收集资源均来源于网络。
可持久化可并堆 - 数据结构
可持久化可并堆一般用于求解 $k$ 短路问题。 如果一种可并堆的时间复杂度不是均摊的,那么它在可持久化后单次操作的时间复杂度就保证是 $O(\log n)$ 的,即不会因为特殊数据而使复杂度退化。 ## 可持久化左偏树 在学习本内容前,请先了解 [左偏树](#) 的相关内容。 回顾左偏树的合并过程,假设我们要合并分别以 $x,y$ 为根节点的两棵左偏树,且维护的左偏树满足小根堆的性质: 1. 如果 $x,y$ 中有结点为空,返回 $x+y$ 。 2. 选择 $x,y$ 两结点中权值更小的结点,作为合并后左偏树的根。 3. 递归合并 $x$ 的右子树与 $y$ ,将合并后的根节点作为 $x$ 的右儿子。 4. 维护当前合并后左偏树的左偏性质,维护 `dist` 值,返回选择的根节点。 由于每次递归都会使 `dist[x]+dist[y]` 减少一,而 `dist[x]` 是 $O(\log n)$ 的,一次最多只会修改 $O(\log n)$ 个结点,所以这样做的时间复杂度是 $O(\log n)$ 的。 可持久化要求保留历史信息,使得之后能够访问之前的版本。要将左偏树可持久化,就要将其沿途修改的路径复制一遍。 所以可持久化左偏树的合并过程是这样的: 1. 如果 $x,y$ 中有结点为空,返回 $x+y$ 。 2. 选择 $x,y$ 两结点中权值更小的结点,新建该结点的一个复制 $p$ ,作为合并后左偏树的根。 3. 递归合并 $p$ 的右子树与 $y$ ,将合并后的根节点作为 $p$ 的右儿子。 4. 维护以 $p$ 为根的左偏树的左偏性质,维护其 `dist` 值,返回 $p$ 。 由于左偏树一次最多只会修改并新建 $O(\log n)$ 个结点,设操作次数为 $m$ ,则可持久化左偏树的时间复杂度和空间复杂度均为 $O(m\log n)$ 。 ### 参考实现 ```cpp int merge(int x, int y) { if (!x || !y) return x + y; if (v[x] > v[y]) swap(x, y); int p = ++cnt; lc[p] = lc[x]; v[p] = v[x]; rc[p] = merge(rc[x], y); if (dist[lc[p]] < dist[rc[p]]) swap(lc[p], rc[p]); dist[p] = dist[rc[p]] + 1; return p; } ```