跳转至

可持久化可並堆

可持久化可並堆一般用於求解 \(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;
}
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用