Bỏ qua

Persistent Mergeable Heap

可持久化可并堆一般用于求解 \(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)\)．

参考实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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;
}

Last updated on this page:, Update history
Found an error? Want to help improve? Edit this page on GitHub!
Contributors to this page:OI-wiki
All content on this page is provided under the terms of the CC BY-SA 4.0 and SATA license, additional terms may apply