可持久化平衡樹

前置知識

OI 常用的可持久化平衡樹 一般就是 可持久化無旋轉 Treap 所以推薦首先學習 無旋轉 Treap。

思想/做法

對於非旋轉 Treap，可通過 Merge 和 Split 操作過程中複製路徑上經過的節點（一般在 Split 操作中複製，確保不影響以前的版本）就可完成可持久化。

對於旋轉 Treap，在複製路徑上經過的節點同時，還需複製受旋轉影響的節點（若其已為這次操作中複製的節點，則無需再複製），對於一次旋轉一般隻影響兩個節點，那麼不會增加其時間複雜度。

上述方法一般被稱為 path copying。

「一切可支持操作都可以通過 Merge Split Newnode Build 完成」，而 Build 操作只用於建造無需理會，Newnode（新建節點）就是用來可持久化的工具。

我們來觀察一下 Merge 和 Split，我們會發現它們都是由上而下的操作！

因此我們完全可以 參考線段樹的可持久化操作 對它進行可持久化。

可持久化操作

可持久化 是對 數據結構 的一種操作，即保留歷史信息，使得在後面可以調用之前的歷史版本。

對於 可持久化線段樹 來説，每一次新建歷史版本就是把 沿途的修改路徑 複製出來

那麼對可持久化 Treap（目前國內 OI 常用的版本）來説：

在複製一個節點 \(X_{a}\)（\(X\) 節點的第 \(a\) 個版本）的新版本 \(X_{a+1}\)（\(X\) 節點的第 \(a+1\) 個版本）以後：

如果某個兒子節點 \(Y\) 不用修改信息，那麼就把 \(X_{a+1}\) 的指針直接指向 \(Y_{a}\)（\(Y\) 節點的第 \(a\) 個版本）即可。
反之，如果要修改 \(Y\)，那麼就在 遞歸到下層 時新建 \(Y_{a+1}\)（\(Y\) 節點的第 \(a+1\) 個版本）這個新節點用於 存儲新的信息，同時把 \(X_{a+1}\) 的指針指向 \(Y_{a+1}\)（\(Y\) 節點的第 \(a+1\) 個版本）。

可持久化

需要的東西：

一個 struct 數組存 每個節點 的信息（一般叫做 tree 數組）；（當然寫 指針版 平衡樹的大佬就可以考慮不用這個數組了）
一個 根節點數組，存每個版本的樹根，每次查詢版本信息時就從 根數組存的節點 開始；
split() 分裂 從樹中分裂出兩棵樹
merge() 合併 把兩棵樹按照隨機權值合併
newNode() 新建一個節點
build() 建樹

Split

對於 分裂操作，每次分裂路徑時 新建節點 指向分出來的路徑，用 std::pair 存新分裂出來的兩棵樹的根。

split(x,k) 返回一個 std::pair;

表示把 \(_x\) 為根的樹的前 \(k\) 個元素放在 一棵樹 中，剩下的節點構成在另一棵樹中，返回這兩棵樹的根（first 是第一棵樹的根，second 是第二棵樹的）。

如果 \(x\) 的 左子樹 的 \(key \geq k\)，那麼 直接遞歸進左子樹，把左子樹分出來的第二顆樹和當前的 \(x\) 右子樹 合併。
否則遞歸 右子樹。

static std::pair<int, int> _split(int _x, int k) {
  if (_x == 0)
    return std::make_pair(0, 0);
  else {
    int _vs = ++_cnt;  // 新建節點（可持久化的精髓）
    _trp[_vs] = _trp[_x];
    std::pair<int, int> _y;
    if (_trp[_vs].key <= k) {
      _y = _split(_trp[_vs].leaf[1], k);
      _trp[_vs].leaf[1] = _y.first;
      _y.first = _vs;
    } else {
      _y = _split(_trp[_vs].leaf[0], k);
      _trp[_vs].leaf[0] = _y.second;
      _y.second = _vs;
    }
    _trp[_vs]._update();
    return _y;
  }
}

Merge

merge(x,y) 返回 merge 出的樹的根。

同樣遞歸實現。如果 x 的隨機權值>y 的隨機權值，則 merge(x_{rc},y)，否則 merge(x,y_{lc})。

static int _merge(int _x, int _y) {
  if (_x == 0 || _y == 0)
    return _x ^ _y;
  else {
    if (_trp[_x].fix < _trp[_y].fix) {
      _trp[_x].leaf[1] = _merge(_trp[_x].leaf[1], _y);
      _trp[_x]._update();
      return _x;
    } else {
      _trp[_y].leaf[0] = _merge(_x, _trp[_y].leaf[0]);
      _trp[_y]._update();
      return _y;
    }
  }
}

例題

洛谷 P3835【模版】可持久化平衡樹

你需要實現一個數據結構，要求提供如下操作（最開始時數據結構內無數據）：

插入 \(x\) 數；
刪除 \(x\) 數（若有多個相同的數，應只刪除一個，如果沒有請忽略該操作）；
查詢 \(x\) 數的排名（排名定義為比當前數小的數的個數 + 1）；
查詢排名為 \(x\) 的數；
求 \(x\) 的前驅（前驅定義為小於 \(x\)，且最大的數，如不存在輸出 \(-2\,147\,483\,647\)）；
求 \(x\) 的後繼（後繼定義為大於 \(x\)，且最小的數，如不存在輸出 \(2\,147\,483\,647\)）。

以上操作均基於某一個歷史版本，同時生成一個新的版本（操作 3, 4, 5, 6 即保持原版本無變化）。而每個版本的編號則為操作的序號。特別地，最初的版本編號為 0。

就是 普通平衡樹 一題的可持久化版，操作和該題類似。

只是使用了可持久化的 merge 和 split 操作。