跳转至

Treap

前置知識：樸素二叉搜索樹

簡介

Treap（樹堆）是一種 弱平衡 的 二叉搜索樹。它同時符合二叉搜索樹和堆的性質，名字也因此為 tree（樹）和 heap（堆）的組合。

其中，二叉搜索樹的性質是：

  • 左子節點的值（\(\textit{val}\)）比父節點小
  • 右子節點的值（\(\textit{val}\)）比父節點大（當然這也是可以反過來的）

堆的性質是：

  • 子節點值（\(\textit{priority}\)）比父節點大或小（取決於是小根堆還是大根堆）

不難看出，如果用的是同一個值，那麼這兩種數據結構在組合後會變成一條鏈，所以我們再在搜索樹的基礎上，引入一個給堆的值 \(\textit{priority}\)。對於 \(\textit{val}\) 值，我們維護搜索樹的性質，對於 \(\textit{priority}\) 值，我們維護堆的性質。其中 \(\textit{priority}\) 這個值是隨機給出的。

下圖就是一個 Treap 的例子（這裏使用的是小根堆，即根節點的值最小）。

那我們為什麼需要大費周章的去讓這個數據結構符合樹和堆的性質，並且隨機給出堆的值呢？

要理解這個，首先需要理解樸素二叉搜索樹的問題。在給樸素搜索樹插入一個新節點時，我們需要從這個搜索樹的根節點開始遞歸，如果新節點比當前節點小，那就向左遞歸，反之亦然。

最後當發現當前節點沒有子節點時，就根據新節點的值的大小，讓新節點成為當前節點的左或右子節點。

如果新插入的節點的值是隨機的，那這個樸素搜索樹的形狀會非常的「胖」，上圖的 Treap 就是一個例子。也就是説，每一層的節點比較多。

在這樣的情況下，這個搜索樹的層數是會比較接近 \(\log_2{n}\)（\(n\) 為節點數）的，查詢的複雜度也是 \(\log_2{n}\)（因為只要遞歸這麼多層就能查到）。

不過，這只是在隨機情況下的複雜度，如果我們按照下面這個非常有序的順序給一個樸素的搜索樹插入節點。

1
1 2 3 4 5

那……

這個樹就會變得非常「瘦長」（每次插入的節點都比前面的大，所以都被安排到右子節點了）：

不難看出，現在這個二叉搜索樹已經退化成鏈了，查詢的複雜度也從 \(\log_2{n}\) 變成了線性。

而 treap 要解決的正是這個問題。它通過隨機化的 \(\textit{priority}\) 屬性，以及維護堆性質的過程，「打亂」了節點的插入順序。從而讓二叉搜索樹達到了理想的複雜度，避免了退化成鏈的問題。

筆者並不清楚如何去嚴格的證明這樣隨機化的過程可以讓搜索樹的複雜度的 期望值 保持在 \(\log_2{n}\)，但我們可以試着感性的去理解一下。

首先，我們需要認識到一個節點的 \(\textit{priority}\) 屬性是和它所在的層數有直接關聯的。再回憶堆的性質：

  • 子節點值（\(\textit{priority}\)）比父節點大或小（取決於是小根堆還是大根堆）

我們發現層數低的節點，比如整個樹的根節點，它的 \(\textit{priority}\) 屬性也會更小（在小根堆中）。並且，在樸素的搜索樹中，先被插入的節點，也更有可能會有比較小的層數。我們可以把這個 \(\textit{priority}\) 屬性和被插入的順序關聯起來理解，這樣，也就理解了為什麼 treap 可以把節點插入的順序通過 \(\textit{priority}\) 打亂。

在給 treap 插入新節點時，需要同時維護樹和堆的性質，為了達到這個目的，有兩種方法被髮明瞭出來，分別是旋轉和分裂、合併。使用這兩種方法的 treap 被分別成為有旋式 treap 和 無旋式 treap。

旋轉 treap

旋轉 treap 維護平衡的方式為旋轉，和 AVL 樹的旋轉操作類似，分為 左旋 和 右旋。即在滿足二叉搜索樹的條件下根據堆的優先級對 treap 進行平衡操作。

旋轉 treap 在做普通平衡樹題的時候，是所有平衡樹中常數較小的。

大部分的樹形數據結構都有指針和數組模擬兩種實現方法，下面將會詳細地講解指針版的代碼，如果想要學習數組實現，可以拉到最下面的完整代碼部分。

Info

注意本代碼中的 rank 代表前面講的 \(\textit{priority}\) 變量（堆的值）。並且，維護的堆的性質是小根堆（\(\textit{priority}\) 小的在上面）。本代碼來源。1

節點結構

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
struct Node {
  Node *ch[2];  // 兩個子節點的地址
  int val, rank;
  int rep_cnt;  // 當前這個值（val）重複出現的次數
  int siz;      // 以當前節點為根的子樹大小

  Node(int val) : val(val), rep_cnt(1), siz(1) {
    ch[0] = ch[1] = nullptr;
    rank = rand();
    // 注意初始化的時候，rank 是隨機給出的
  }

  void upd_siz() {
    // 用於旋轉和刪除過後，重新計算 siz 的值
    siz = rep_cnt;
    if (ch[0] != nullptr) siz += ch[0]->siz;
    if (ch[1] != nullptr) siz += ch[1]->siz;
  }
};

旋轉

旋轉操作是 treap 的一個非常重要的操作，主要用來在保持 treap 樹性質的同時，調整不同節點的層數，以達到維護堆性質的作用。

旋轉操作的左旋和右旋可能不是特別容易區分，以下是兩個較為明顯的特點：

旋轉操作的含義：

  • 在不影響搜索樹性質的前提下，把和旋轉方向相反的子樹變成根節點（如左旋，就是把右子樹變成根節點）
  • 不影響性質，並且在旋轉過後，跟旋轉方向相同的子節點變成了原來的根節點（如左旋，旋轉完之後的左子節點是旋轉前的根節點）

左旋和右旋操作是相互的，如下圖。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
enum rot_type { LF = 1, RT = 0 };

void _rotate(Node *&cur,
             rot_type dir) {  // dir參數代表旋轉的方向 0為右旋，1為左旋
  // 注意傳進來的 cur 是指針的引用，也就是改了這個
  // cur，變量是跟着一起改的，如果這個 cur 是別的 樹的子節點，根據 ch
  // 找過來的時候，也是會找到這裏的

  // 以下的代碼解釋的均是左旋時的情況
  Node *tmp = cur->ch[dir];  // 讓 C 變成根節點，
                             // 這裏的 tmp
                             // 是一個臨時的節點指針，指向成為新的根節點的節點

  /* 左旋：也就是讓右子節點變成根節點
   *         A                 C
   *        / \               / \
   *       B  C    ---->     A   E
   *         / \            / \
   *        D   E          B   D
   */
  cur->ch[dir] = tmp->ch[!dir];    // 讓 A 的右子節點變成 D
  tmp->ch[!dir] = cur;             // 讓 C 的左子節點變成 A
  cur->upd_siz(), tmp->upd_siz();  // 更新大小信息
  cur = tmp;  // 最後把臨時儲存 C 樹的變量賦值到當前根節點上（注意 cur 是引用）
}

插入

跟普通搜索樹插入的過程沒啥區別，但是需要在插的過程中通過旋轉來維護樹堆中堆的性質。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
void _insert(Node *&cur, int val) {
  if (cur == nullptr) {
    // 沒這個節點直接新建
    cur = new Node(val);
    return;
  } else if (val == cur->val) {
    // 如果有這個值相同的節點，就把重複數量加一
    cur->rep_cnt++;
    cur->siz++;
  } else if (val < cur->val) {
    // 維護搜索樹性質，val 比當前節點小就插到左邊，反之亦然
    _insert(cur->ch[0], val);
    if (cur->ch[0]->rank < cur->rank) {
      // 小根堆中，上面節點的優先級一定更小
      // 因為新插的左子節點比父節點小，現在需要讓左子節點變成父節點
      _rotate(cur, RT);  // 注意前面的旋轉性質，要把左子節點轉上來，需要右旋
    }
    cur->upd_siz();  // 插入之後大小會變化，需要更新
  } else {
    _insert(cur->ch[1], val);
    if (cur->ch[1]->rank < cur->rank) {
      _rotate(cur, LF);
    }
    cur->upd_siz();
  }
}

刪除

主要就是分類討論，不同的情況有不同的處理方法，刪完了樹的大小會有變化，要注意更新。並且如果要刪的節點有左子樹和右子樹，就要考慮刪除之後讓誰來當父節點（維護 rank 小的節點在上面）。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
void _del(Node *&cur, int val) {
  if (val > cur->val) {
    _del(cur->ch[1], val);
    // 值更大就在右子樹，反之亦然
    cur->upd_siz();
  } else if (val < cur->val) {
    _del(cur->ch[0], val);
    cur->upd_siz();
  } else {
    if (cur->rep_cnt > 1) {
      // 如果要刪除的節點是重複的，可以直接把重複值減小
      cur->rep_cnt--, cur->siz--;
      return;
    }
    uint8_t state = 0;
    state |= (cur->ch[0] != nullptr);
    state |= ((cur->ch[1] != nullptr) << 1);
    // 00都無，01有左無右，10，無左有右，11都有
    Node *tmp = cur;
    switch (state) {
      case 0:
        delete cur;
        cur = nullptr;
        // 沒有任何子節點，就直接把這個節點刪了
        break;
      case 1:  // 有左無右
        cur = tmp->ch[0];
        // 把根變成左兒子，然後把原來的根節刪了，注意這裏的 tmp 是從 cur
        // 複製的，而 cur 是引用
        delete tmp;
        break;
      case 2:  // 有右無左
        cur = tmp->ch[1];
        delete tmp;
        break;
      case 3:
        rot_type dir = cur->ch[0]->rank < cur->ch[1]->rank
                           ? RT
                           : LF;  // dir 是 rank 更小的那個兒子
        _rotate(cur, dir);  // 這裏的旋轉可以把優先級更小的兒子轉上去，rt 是 0，
                            // 而 lf 是 1，剛好跟實際的子樹下標反過來
        _del(
            cur->ch[!dir],
            val);  // 旋轉完成後原來的根節點就在旋方向那邊，所以需要
                   // 繼續把這個原來的根節點刪掉
                   // 如果説要刪的這個節點是在整個樹的「上層的」，那我們會一直通過這
                   // 這裏的旋轉操作，把它轉到沒有子樹了（或者只有一個），再刪掉它。
        cur->upd_siz();
        // 刪除會造成大小改變
        break;
    }
  }
}

根據值查詢排名

操作含義：查詢以 cur 為根節點的子樹中，val 這個值的大小的排名（該子樹中小於 val 的節點的個數 + 1）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
int _query_rank(Node *cur, int val) {
  int less_siz = cur->ch[0] == nullptr ? 0 : cur->ch[0]->siz;
  // 這個樹中小於 val 的節點的數量
  if (val == cur->val)
    // 如果這個節點就是要查的節點
    return less_siz + 1;
  else if (val < cur->val) {
    if (cur->ch[0] != nullptr)
      return _query_rank(cur->ch[0], val);
    else
      return 1;  // 如果左子樹是空的，説比最小的節點還要小，那這個數字就是最小的
  } else {
    if (cur->ch[1] != nullptr)
      // 如果要查的值比這個節點大，那這個節點的左子樹以及這個節點自身肯定都比要查的值小
      // 所以要加上這兩個值，再加上往右邊找的結果
      // （以右子樹為根的子樹中，val 這個值的大小的排名）
      return less_siz + cur->rep_cnt + _query_rank(cur->ch[1], val);
    else
      return cur->siz + 1;
    // 沒有右子樹的話直接整個樹 + 1 相當於 less_siz + cur->rep_cnt + 1
  }
}

根據排名查詢值

要根據排名查詢值，我們首先要知道如何判斷要查的節點在樹的哪個部分：

以下是一個判斷方法的表：

左子樹 根節點/當前節點 右子樹
排名 ≤ 左子樹的大小 排名 > 左子樹的大小，並且 ≤ 左子樹的大小 + 根節點的重複次數 排名 > 左子樹的大小 + 根節點的重複次數

注意如果在右子樹，遞歸的時候需要對原來的 rank 進行處理。遞歸的時候就相當去查，在右子樹中為這個排名的值，為了把排名轉換成基於右子樹的，需要把原來的 rank 減去左子樹的大小和根節點的重複次數。

可以把所有節點想象成一個排好序的數組，或者數軸（如下），

1
2
3
4
5
6
7
1 -> |左子樹的節點|根節點|右子樹的節點| -> n
                           ^
                           要查的排名
                     ⬇轉換成基於右子樹的排名
1 -> |右子樹的節點| -> n
       ^
       要查的排名

這裏的轉換方法就是直接把排名減去左子樹的大小和根節點的重複數量。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
int _query_val(Node *cur, int rank) {
  // 查詢樹中第 rank 大的節點的值
  int less_siz = cur->ch[0] == nullptr ? 0 : cur->ch[0]->siz;
  // less siz 是左子樹的大小
  if (rank <= less_siz)
    return _query_val(cur->ch[0], rank);
  else if (rank <= less_siz + cur->rep_cnt)
    return cur->val;
  else
    return _query_val(cur->ch[1], rank - less_siz - cur->rep_cnt);  // 見前文
}

查詢第一個比 val 小的節點

注意這裏使用了一個類中的全局變量，q_prev_tmp。

這個值是隻有在 val 比當前節點值大的時候才會被更改的，所以返回這個變量就是返回 val 最後一次比當前節點的值大，之後就是更小了。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
int _query_prev(Node *cur, int val) {
  if (val <= cur->val) {
    // 還是比 val 大，所以往左子樹找
    if (cur->ch[0] != nullptr) return _query_prev(cur->ch[0], val);
  } else {
    // 只有能進到這個 else 裏，才會更新 q_prev_tmp 的值
    q_prev_tmp = cur->val;
    // 當前節點已經比 val，小了，但是不確定是否是最大的，所以要到右子樹繼續找
    if (cur->ch[1] != nullptr) _query_prev(cur->ch[1], val);
    // 接下來的遞歸可能不會更改 q_prev_tmp
    // 了，那就直接返回這個值，總之返回的就是最後一次進到 這個 else 中的
    // cur->val
    return q_prev_tmp;
  }
  return -1145;
}

查詢第一個比 val 大的節點

跟前一個很相似，只是大於小於號換了一下。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
int _query_nex(Node *cur, int val) {
  if (val >= cur->val) {
    if (cur->ch[1] != nullptr) return _query_nex(cur->ch[1], val);
  } else {
    q_nex_tmp = cur->val;
    if (cur->ch[0] != nullptr) _query_nex(cur->ch[0], val);
    return q_nex_tmp;
  }
  return -1145;
}

無旋 treap

無旋 treap 的操作方式使得它天生支持維護序列、可持久化等特性。

無旋 treap 又稱分裂合併 treap。它僅有兩種核心操作，即為 分裂 與 合併。通過這兩種操作，在很多情況下可以比旋轉 treap 更方便的實現別的操作。下面逐一介紹這兩種操作。

註釋

講解無旋 treap 應當提到 FHQ-Treap（by 範浩強）。即可持久化，支持區間操作的無旋 Treap。更多內容請參照《範浩強談數據結構》ppt。

分裂（split）

按值分裂

分裂過程接受兩個參數：根指針 \(\textit{cur}\)、關鍵值 \(\textit{key}\)。結果為將根指針指向的 treap 分裂為兩個 treap，第一個 treap 所有結點的值（\(\textit{val}\)）小於等於 \(\textit{key}\)，第二個 treap 所有結點的值大於 \(\textit{key}\)。

該過程首先判斷 \(\textit{key}\) 是否小於 \(\textit{cur}\) 的值，若小於，則説明 \(\textit{cur}\) 及其右子樹全部大於 \(\textit{key}\)，屬於第二個 treap。當然，也可能有一部分的左子樹的值大於 \(\textit{key}\)，所以還需要繼續向左子樹遞歸地分裂。對於大於 \(\textit{key}\) 的那部分左子樹，我們把它作為 \(\textit{cur}\) 的左子樹，這樣，整個 \(\textit{cur}\) 上的節點都是大於 \(\textit{key}\) 的。

相應的，如果 \(\textit{key}\) 大於等於 \(\textit{cur}\) 的值，説明 \(\textit{cur}\) 的整個左子樹以及其自身都小於 \(\textit{key}\)，屬於分裂後的第一個 treap。並且，\(\textit{cur}\) 的部分右子樹也可能有部分小於 \(\textit{key}\)，因此我們需要繼續遞歸地分裂右子樹。把小於 \(\textit{key}\) 的那部分作為 \(\textit{cur}\) 的右子樹，這樣，整個 \(\textit{cur}\) 上的節點都小於 \(\textit{key}\)。

下圖展示了 \(\textit{cur}\) 的值小於等於 \(\textit{key}\) 時按值分裂的情況。2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
pair<Node *, Node *> split(Node *cur, int key) {
  if (cur == nullptr) return {nullptr, nullptr};
  if (cur->val <= key) {
    // cur 以及它的左子樹一定屬於分裂後的第一個樹
    auto temp = split(cur->ch[1], key);
    // 但是它可能有部分右子樹也比 key 小
    cur->ch[1] = temp.first;
    // 我們把小於 key 的那部分拿出來，作為 cur 的右子樹，這樣整個 cur 都是小於
    // key 的 剩下的那部分右子樹成為分裂後的第二個 treap
    cur->upd_siz();
    // 分裂過後樹的大小會變化，需要更新
    return {cur, temp.second};
  } else {
    // 同上
    auto temp = split(cur->ch[0], key);
    cur->ch[0] = temp.second;
    cur->upd_siz();
    return {temp.first, cur};
  }
}

按排名分裂

比起按值分裂，這個操作更像是旋轉 treap 中的根據排名（某個節點的排名是樹中所有小於此節點值的節點的數量 \(+ 1\)）查詢值：

此函數接受兩個參數，節點指針 \(\textit{cur}\) 和排名 \(\textit{rk}\)，返回分裂後的三個 treap。

其中，第一個 treap 中每個節點的排名都小於 \(\textit{rk}\)，第二個的排名等於 \(\textit{rk}\)，並且第二個 treap 只有一個節點（不可能有多個等於的，如果有的話會增加 Node 結構體中的 cnt），第三個則是大於。

此操作的重點在於判斷排名和 \(\textit{cur}\) 相等的節點在樹的哪個部分，這也是旋轉 treap 根據排名查詢值操作時的重要部分，在前文有非常詳細的解釋，這裏不過多講解。

並且，此操作的遞歸部分和按值分裂也非常相似，這裏不贅述。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
tuple<Node *, Node *, Node *> split_by_rk(Node *cur, int rk) {
  if (cur == nullptr) return {nullptr, nullptr, nullptr};
  int ls_siz = cur->ch[0] == nullptr ? 0 : cur->ch[0]->siz;
  if (rk <= ls_siz) {
    // 排名和 cur 相等的節點在左子樹
    Node *l, *mid, *r;
    tie(l, mid, r) = split_by_rk(cur->ch[0], rk);
    cur->ch[0] = r;  // 返回的第三個 treap 中的排名都大於 rk
    // cur 的左子樹被設成 r 後，整個 cur 中節點的排名都大於 rk
    cur->upd_siz();
    return {l, mid, cur};
  } else if (rk <= ls_siz + cur->cnt) {
    // 和 cur 相等的就是當前節點
    Node *lt = cur->ch[0];
    Node *rt = cur->ch[1];
    cur->ch[0] = cur->ch[1] = nullptr;
    // 分裂後第二個 treap 只有一個節點，所有要把它的子樹設置為空
    return {lt, cur, rt};
  } else {
    // 排名和 cur 相等的節點在右子樹
    // 遞歸過程同上
    Node *l, *mid, *r;
    tie(l, mid, r) = split_by_rk(cur->ch[1], rk - ls_siz - cur->cnt);
    cur->ch[1] = l;
    cur->upd_siz();
    return {cur, mid, r};
  }
}

合併（merge）

合併過程接受兩個參數：左 treap 的根指針 \(\textit{u}\)、右 treap 的根指針 \(\textit{v}\)。必須滿足 \(\textit{u}\) 中所有結點的值小於等於 \(\textit{v}\) 中所有結點的值。一般來説，我們合併的兩個 treap 都是原來從一個 treap 中分裂出去的，所以不難滿足 \(\textit{u}\) 中所有節點的值都小於 \(\textit{v}\)

在旋轉 treap 中，我們藉助旋轉操作來維護 \(\textit{priority}\) 符合堆的性質，同時旋轉時還不能改變樹的性質。在無旋 treap 中，我們用合併達到相同的效果。

因為兩個 treap 已經有序，所以我們在合併的時候只需要考慮把哪個樹「放在上面」，把哪個「放在下面」，也就是是需要判斷將哪個一個樹作為子樹。顯然，根據堆的性質，我們需要把 \(\textit{priority}\) 小的放在上面（這裏採用小根堆）。

同時，我們還需要滿足搜索樹的性質，所以若 \(\textit{u}\) 的根結點的 \(\textit{priority}\) 小於 \(\textit{v}\) 的，那麼 \(\textit{u}\) 即為新根結點，並且 \(\textit{v}\) 因為值比 \(\textit{u}\) 更大，應與 \(\textit{u}\) 的右子樹合併；反之，則 \(\textit{v}\) 作為新根結點，然後因為 \(u\) 的值比 \(\textit{v}\) 小，與 \(v\) 的左子樹合併。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
Node *merge(Node *u, Node *v) {
  // 傳進來的兩個樹的內部已經符合搜索樹的性質了
  // 並且 u 內所有節點的值 < v 內所有節點的值
  // 所以在合併的時候需要維護堆的性質
  // 這裏用的是小根堆
  if (u == nullptr && v == nullptr) return nullptr;
  if (u != nullptr && v == nullptr) return u;
  if (v != nullptr && u == nullptr) return v;

  if (u->prio < v->prio) {
    // u 的 prio 比較小，u應該作為父節點
    u->ch[1] = merge(u->ch[1], v);
    // 因為 v 比 u 大，所以把 v 作為 u 的右子樹
    u->upd_siz();
    return u;
  } else {
    // v 比較小，v應該作為父節點
    v->ch[0] = merge(u, v->ch[0]);
    // u 比 v 小，所以遞歸時的參數是這樣的
    v->upd_siz();
    return v;
  }
}

插入

在無旋 treap 中，插入，刪除，根據值查詢排名等基礎操作既可以用普通二叉查找樹的方法實現，也可以用分裂和合並來實現。通常來説，使用分裂和合並來實現更加簡潔，但是速度會慢一點3。為了幫助更好的理解無旋 treap，下面的操作全部使用分裂和合並實現。

在實現插入操作時，我們利用了分裂操作的一些性質。也就是值小於等於 \(\textit{val}\) 的節點會被分到第一個 treap。

所以，假設我們根據 \(\textit{val}\) 分裂當前這個 treap。會有下面兩棵樹，並符合以下條件：

\[ \begin{aligned} T_1 &\le val\\ T_2 &> val \end{aligned} \]

其中 \(T_1\) 表示分裂後所有被分到第一個 treap 的節點的集合，\(T_2\) 則是第二個。

如果我們再按照 \(\textit{val} - 1\) 繼續分裂 \(T_1\)，那麼會產生下面兩棵樹，並符合以下條件：

\[ \begin{gathered} T_{1\ \text{left}} \le val - 1\\ T_{1\ \text{right}} > val - 1 \ \And \ T_{1\ \text{right}} \le val \end{gathered} \]

其中 \(T_{1\ \text{left}}\) 表示 \(T_1\) 分裂後所有被分到第一個 treap 的節點的集合，\(T_{1\ \text{right}}\) 則是第二個。並且上面的式子中，後半部分的 \(\And \ T_{1\ \text{right}} \le val\) 來自於 \(T_1\) 所符合的條件 \(T_1 \le val\)。

不難發現，只要 \(\textit{val}\) 和節點的值是一個整數（大多數使用場景下會使用整數）那麼符合 \(T_{1\ \text{right}}\) 條件的節點只有一個，也就是值等於 \(\textit{val}\) 的節點。

在插入時，如果我們發現符合 \(T_{1\ \text{right}}\) 的節點存在，那就可以直接增加重複次數，否則，就新開一個節點。

注意把樹分裂好了還需要用合併操作把它「粘」回去，這樣下次還能繼續使用。並且，還需要注意合併操作的參數順序是有要求的，第一個樹的所有節點的值都需要小於第二個。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
void insert(int val) {
  auto temp = split(root, val);
  // 根據 val 的值把整個樹分成兩個
  // 注意 split 的實現，等於 val 的子樹是在左子樹的
  auto l_tr = split(temp.first, val - 1);
  // l_tr 的左子樹 <= val - 1，如果有 = val 的節點，那一定在右子樹
  Node *new_node;
  if (l_tr.second == nullptr) {
    // 沒有這個節點就新開，否則直接增加重複次數。
    new_node = new Node(val);
  } else {
    l_tr.second->cnt++;
    l_tr.second->upd_siz();
  }
  Node *l_tr_combined =
      merge(l_tr.first, l_tr.second == nullptr ? new_node : l_tr.second);
  // 合併 T_1 left 和 T_1 right
  root = merge(l_tr_combined, temp.second);
  // 合併 T_1 和 T_2
}

刪除

刪除操作也使用和插入操作相似的方法，找到值和 \(\textit{val}\) 相等的節點，並且刪除它。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
void del(int val) {
  auto temp = split(root, val);
  auto l_tr = split(temp.first, val - 1);
  if (l_tr.second->cnt > 1) {
    // 如果這個節點的重複次數大於 1，減小即可
    l_tr.second->cnt--;
    l_tr.second->upd_siz();
    l_tr.first = merge(l_tr.first, l_tr.second);
  } else {
    if (temp.first == l_tr.second) {
      // 有可能整個 T_1 只有這個節點，所以也需要把這個點設成 null 來標註已經刪除
      temp.first = nullptr;
    }
    delete l_tr.second;
    l_tr.second = nullptr;
  }
  root = merge(l_tr.first, temp.second);
}

根據值查詢排名

排名是比這個值小的節點的數量 \(+ 1\)，所以我們根據 \(\textit{val} - 1\) 分裂當前樹，那麼分裂後的第一個樹就符合：

\[ T_1 \le val - 1 \]

如果樹的值和 \(\textit{val}\) 為整數，那麼 \(T_1\) 就包含了所有值小於 \(\textit{val}\) 的節點。

1
2
3
4
5
6
int qrank_by_val(Node* cur, int val) {
  auto temp = split(cur, val - 1);
  int ret = (temp.first == nullptr ? 0 : temp.first->siz) + 1;  // 根據定義 + 1
  root = merge(temp.first, temp.second);  // 拆好了再粘回去
  return ret;
}

根據排名查詢值

調用 split_by_rk() 函數後，會返回分裂好的三個 treap，其中第二個只包含一個節點，它的排名等於 \(\textit{rk}\)，所以我們直接返回這個節點的 \(\textit{val}\)。

1
2
3
4
5
6
7
int qval_by_rank(Node *cur, int rk) {
  Node *l, *mid, *r;
  tie(l, mid, r) = split_by_rk(cur, rk);
  int ret = mid->val;
  root = merge(merge(l, mid), r);
  return ret;
}

查詢第一個比 val 小的節點

可以把這個問題轉化為，在比 \(\textit{val}\) 小的所有節點中，找出排名最大的。我們根據 \(\textit{val}\) 來分裂這個 treap，返回的第一個 treap 中的節點的值就全部小於 \(\textit{val}\)，然後我們調用 qval_by_rank() 找出這個樹中值最大的節點。

1
2
3
4
5
6
7
8
int qprev(int val) {
  auto temp = split(root, val - 1);
  // temp.first 就是值小於 val 的子樹
  int ret = qval_by_rank(temp.first, temp.first->siz);
  // 這裏查詢的是，所有小於 val 的節點裏面，最大的那個的值
  root = merge(temp.first, temp.second);
  return ret;
}

查詢第一個比 val 大的節點

和上個操作類似，可以把這個問題轉化為，在比 \(\textit{val}\) 大的所有節點中，找出排名最大的。那麼根據 \(\textit{val}\) 分裂後，返回的第二個 treap 中的所有節點的值就大於 \(\textit{val}\)。

然後我們去查詢這個樹中排名為 \(1\) 的節點（也就是值最小的節點）的值，就可以成功查到第一個比 \(\textit{val}\) 大的節點。

1
2
3
4
5
6
7
int qnex(int val) {
  auto temp = split(root, val);
  int ret = qval_by_rank(temp.second, 1);
  // 查詢所有大於 val 的子樹裏面，值最小的那個
  root = merge(temp.first, temp.second);
  return ret;
}

建樹（build）

將一個有 \(n\) 個節點的序列 \(\{a_n\}\) 轉化為一棵 treap。

可以依次暴力插入這 \(n\) 個節點，每次插入一個權值為 \(v\) 的節點時，將整棵 treap 按照權值分裂成權值小於等於 \(v\) 的和權值大於 \(v\) 的兩部分，然後新建一個權值為 \(v\) 的節點，將兩部分和新節點按從小到大的順序依次合併，單次插入時間複雜度 \(O(\log n)\)，總時間複雜度 \(O(n\log n)\)。

在某些題目內，可能會有多次插入一段有序序列的操作，這是就需要在 \(O(n)\) 的時間複雜度內完成建樹操作。

方法一：在遞歸建樹的過程中，每次選取當前區間的中點作為該區間的樹根，並對每個節點欽定合適的優先值，使得新樹滿足堆的性質。這樣能保證樹高為 \(O(\log n)\)。

方法二：在遞歸建樹的過程中，每次選取當前區間的中點作為該區間的樹根，然後給每個節點一個隨機優先級。這樣能保證樹高為 \(O(\log n)\)，但不保證其滿足堆的性質。這樣也是正確的，因為無旋式 treap 的優先級是用來使 merge 操作更加隨機一點，而不是用來保證樹高的。

方法三：觀察到 treap 是笛卡爾樹，利用笛卡爾樹的 \(O(n)\) 建樹方法即可，用單調棧維護右鏈即可。

無旋 treap 的區間操作

建樹

無旋 treap 相比旋轉 treap 的一大好處就是可以實現各種區間操作，下面我們以文藝平衡樹的 模板題 為例，介紹 treap 的區間操作。

您需要寫一種數據結構（可參考題目標題），來維護一個有序數列。

其中需要提供以下操作：翻轉一個區間，例如原有序序列是 \(5\ 4\ 3\ 2\ 1\)，翻轉區間是 \([2,4]\) 的話，結果是 \(5\ 2\ 3\ 4\ 1\)。 對於 \(100\%\) 的數據，\(1 \le n\)（初始區間長度）\(m\)（翻轉次數）\(\le 1e5\)

在這道題目中，我們需要實現的是區間翻轉，那麼我們首先需要考慮如何建樹，建出來的樹需要是初始的區間。

我們只需要把區間的下標依次插入 treap 中，這樣在中序遍歷（先遍歷左子樹，然後當前節點，最後右子樹）時，就可以得到這個區間4。

我們知道在樸素的二叉查找樹中按照遞增的順序插入節點，建出來的樹是一個長鏈，按照中序遍歷，自然可以得到這個區間。

如上圖，按照 \(1\ 2\ 3\ 4\ 5\) 的順序給樸素搜索樹插入節點，中序遍歷時，得到的也是 \(1\ 2\ 3\ 4\ 5\)。

但是在 treap 中，按增序插入節點後，在合併操作時還會根據 \(\textit{priority}\) 調整樹的結構，在這樣的情況下，如何確保中序遍歷一定能正確的輸出呢？

可以參考 笛卡爾樹的單調棧建樹方法 來理解這個問題。

設新插入的節點為 \(\textit{u}\)。

首先，因為是遞增地插入節點，每一個新插入的節點肯定會被連接到 treap 的右鏈（即從根結點一直往右子樹走，經過的結點形成的鏈）上。

從根節點開始，右鏈上的節點的 \(\textit{priority}\) 是遞增的（小根堆）。那我們可以找到右鏈上第一個 \(\textit{priority}\) 大於 \(\textit{u}\) 的節點，我們叫這個節點 \(\textit{v}\)，並把這個節點換成 \(\textit{u}\)。

因為 \(\textit{u}\) 一定大於這個樹上其他的全部節點，我們需要把 \(\textit{v}\) 以及它的子樹作為 \(\textit{u}\) 的左子樹。並且此時 \(\textit{u}\) 沒有右子樹。

可以發現，中序遍歷時 \(\textit{u}\) 一定是最後一個被遍歷到的（因為 \(\textit{u}\) 是右鏈中的最後一個，而中序遍歷中，右子樹是最後被遍歷到的）。

下圖是一個 treap 根據遞增順序插入 \(1 \sim 5\) 號節點時，插入 \(5\) 號節點時的變化，可以用這張圖更好的理解按照增序插入的過程。

區間翻轉

翻轉 \([l, r]\) 這個區間時，基本思路是將樹分裂成 \([1, l - 1],\ [l, r],\ [r + 1, n]\) 三個區間，再對中間的 \([l, r]\) 進行翻轉4。

翻轉的具體操作是把區間內的子樹的每一個左，右子節點交換位置。如下圖就展示了翻轉上圖中 treap 的 \([3, 4]\) 和 \([3, 5]\) 區間後的 treap。

注意如果按照這個方法翻轉，那麼每次翻轉 \([l, r]\) 區間時，就會有 \(r - l\) 個節點會被交換位置，這樣頻繁的操作顯然不能滿足 \(10^5\) 的數據範圍，其 \(O(n \times \log_2 n)\) 的單次翻轉複雜度甚至不如暴力（因為我們除了需要花線性時間交換節點外，還需要在樹中花費 \(O(\log_2 n)\) 的時間找到需要交換的節點）。

再觀察題目要求，可以發現因為只需要最後輸出操作完的區間，所以並不需要每次都真的去交換。如此一來，便可以使用線段樹中常用的懶標記（lazy tag）來優化複雜度。交換時，只需要在父節點打上標記，代表這個子樹下的每個左右子節點都需要交換就行了。

在線段樹中，我們一般在更新和查詢時下傳懶標記。這是因為，在更新和查詢時，我們想要更新/查詢的範圍不一定和懶標記代表的範圍重合，所以要先下傳標記，確保查到和更新後的值是正確的。

在無旋 treap 中也是一樣。具體操作時我們會把 treap 分裂成前文講到的三個樹，然後給中間的樹打上懶標記後合併這三棵樹。因為我們想要翻轉的區間和懶標記代表的區間不一定重合，所以要在分裂時下傳標記。並且，分裂和合並操作會造成每個節點及其懶標記所代表的節點發生變動，所以也需要在合併前下傳懶標記。

換句話説，是當樹的結構發生改變的時候，當我們進行分裂或合併操作時需要改變某一個點的左右兒子信息時之前，應該下放標記，而非之後，因為懶標記是需要下傳給兒子節點的，但更改左右兒子信息之後若懶標記還未下放，則懶標記就丟失了下放的對象。5

以下為代碼講解，代碼參考了4。

因為區間操作中大部分操作都和普通的無旋 treap 相同，所以這裏只講解和普通無旋 treap 不同的地方。

下傳標記

需要注意這裏的懶標記代表需要把這個樹中的每一個子節點交換位置。所以如果當前節點的子節點也有懶標記，那兩次翻轉就抵消了。如果子節點不需要翻轉，那麼這個懶標記就需要繼續被下傳到子節點上。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
// 這裏這個 pushdown 是 Node 類的成員函數，其中 to_rev 是懶標記
void pushdown() {
  swap(ch[0], ch[1]);
  if (ch[0] != nullptr) ch[0]->to_rev ^= 1;
  if (ch[1] != nullptr) ch[1]->to_rev ^= 1;
  to_rev = false;
}

void check_tag() {
  if (to_rev) pushdown();
}

分裂

注意在這個題目中，因為翻轉操作，treap 中的 \(\textit{val}\) 會不符合二叉搜索樹的性質（見區間翻轉部分的圖），所以我們不能根據 \(\textit{val}\) 來判斷應該往左子樹還是右子樹遞歸。

所以這裏的分裂跟普通無旋 treap 中的按排名分裂更相似，是根據當前樹的大小判斷往左還是右子樹遞歸的，換言之，我們是按照開始時這個節點在樹中的位置來判斷的。

返回的第一個 treap 中節點的排名全部小於等於 \(\textit{sz}\)，而第二個 treap 中節點的排名則全部大於 \(\textit{sz}\)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
#define siz(_) (_ == nullptr ? 0 : _->siz)

pair<Node*, Node*> split(Node* cur, int sz) {
  // 按照樹的大小判斷
  if (cur == nullptr) return {nullptr, nullptr};
  cur->check_tag();
  // 分裂前先下傳
  if (sz <= siz(cur->ch[0])) {
    auto temp = split(cur->ch[0], sz);
    cur->ch[0] = temp.second;
    cur->upd_siz();
    return {temp.first, cur};
  } else {
    auto temp =
        split(cur->ch[1],
              sz - siz(cur->ch[0]) -
                  1);  // 這裏的轉換在有旋 treap 的 「根據排名查詢值有講」
    cur->ch[1] = temp.first;
    cur->upd_siz();
    return {cur, temp.second};
  }
}

合併

唯一需要注意的是在合併前下傳懶標記

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
Node *merge(Node *sm, Node *bg) {
  // small, big
  if (sm == nullptr && bg == nullptr) return nullptr;
  if (sm != nullptr && bg == nullptr) return sm;
  if (sm == nullptr && bg != nullptr) return bg;
  sm->check_tag(), bg->check_tag();
  if (sm->prio < bg->prio) {
    sm->ch[1] = merge(sm->ch[1], bg);
    sm->upd_siz();
    return sm;
  } else {
    bg->ch[0] = merge(sm, bg->ch[0]);
    bg->upd_siz();
    return bg;
  }
}

區間翻轉

和前面介紹的一樣，分裂出 \([1, l - 1],\ [l, r],\ [r + 1, n]\) 三個區間，然後對中間的區間打上標記後再合併。

1
2
3
4
5
6
7
8
9
void seg_rev(int l, int r) {
  // 這裏的 less 和 more 是相對於 l 的
  auto less = split(root, l - 1);
  // 所有小於等於 l - 1 的會在 less 的左子樹
  auto more = split(less.second, r - l + 1);
  // 從 l 開始的前 r - l + 1 個元素的區間
  more.first->to_rev = true;
  root = merge(less.first, merge(more.first, more.second));
}

中序遍歷打印

要注意在打印時要下傳標記。

1
2
3
4
5
6
7
8
void print(Node* cur) {
  if (cur == nullptr) return;
  cur->check_tag();
  // 中序遍歷 -> 先左子樹，再自己，最後右子樹
  print(cur->ch[0]);
  cout << cur->val << " ";
  print(cur->ch[1]);
}

完整代碼

旋轉 treap

指針實現

完整代碼

以下是前文講解的代碼的完整版本，是普通平衡樹的模板代碼。

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
// author: (ttzytt)[ttzytt.com]
#include <bits/stdc++.h>
using namespace std;

struct Node {
  Node *ch[2];
  int val, rank;
  int rep_cnt;
  int siz;

  Node(int val) : val(val), rep_cnt(1), siz(1) {
    ch[0] = ch[1] = nullptr;
    rank = rand();
  }

  void upd_siz() {
    siz = rep_cnt;
    if (ch[0] != nullptr) siz += ch[0]->siz;
    if (ch[1] != nullptr) siz += ch[1]->siz;
  }
};

class Treap {
 private:
  Node *root;

  enum rot_type { LF = 1, RT = 0 };

  int q_prev_tmp = 0, q_nex_tmp = 0;

  void _rotate(Node *&cur, rot_type dir) {  // 0為右旋，1為左旋
    Node *tmp = cur->ch[dir];
    cur->ch[dir] = tmp->ch[!dir];
    tmp->ch[!dir] = cur;
    cur->upd_siz(), tmp->upd_siz();
    cur = tmp;
  }

  void _insert(Node *&cur, int val) {
    if (cur == nullptr) {
      cur = new Node(val);
      return;
    } else if (val == cur->val) {
      cur->rep_cnt++;
      cur->siz++;
    } else if (val < cur->val) {
      _insert(cur->ch[0], val);
      if (cur->ch[0]->rank < cur->rank) {
        _rotate(cur, RT);
      }
      cur->upd_siz();
    } else {
      _insert(cur->ch[1], val);
      if (cur->ch[1]->rank < cur->rank) {
        _rotate(cur, LF);
      }
      cur->upd_siz();
    }
  }

  void _del(Node *&cur, int val) {
    if (val > cur->val) {
      _del(cur->ch[1], val);
      cur->upd_siz();
    } else if (val < cur->val) {
      _del(cur->ch[0], val);
      cur->upd_siz();
    } else {
      if (cur->rep_cnt > 1) {
        cur->rep_cnt--, cur->siz--;
        return;
      }
      uint8_t state = 0;
      state |= (cur->ch[0] != nullptr);
      state |= ((cur->ch[1] != nullptr) << 1);
      // 00都無，01有左無右，10，無左有右，11都有
      Node *tmp = cur;
      switch (state) {
        case 0:
          delete cur;
          cur = nullptr;
          break;
        case 1:  // 有左無右
          cur = tmp->ch[0];
          delete tmp;
          break;
        case 2:  // 有右無左
          cur = tmp->ch[1];
          delete tmp;
          break;
        case 3:
          rot_type dir = cur->ch[0]->rank < cur->ch[1]->rank ? RT : LF;
          _rotate(cur, dir);
          _del(cur->ch[!dir], val);
          cur->upd_siz();
          break;
      }
    }
  }

  int _query_rank(Node *cur, int val) {
    int less_siz = cur->ch[0] == nullptr ? 0 : cur->ch[0]->siz;
    if (val == cur->val)
      return less_siz + 1;
    else if (val < cur->val) {
      if (cur->ch[0] != nullptr)
        return _query_rank(cur->ch[0], val);
      else
        return 1;
    } else {
      if (cur->ch[1] != nullptr)
        return less_siz + cur->rep_cnt + _query_rank(cur->ch[1], val);
      else
        return cur->siz + 1;
    }
  }

  int _query_val(Node *cur, int rank) {
    int less_siz = cur->ch[0] == nullptr ? 0 : cur->ch[0]->siz;
    if (rank <= less_siz)
      return _query_val(cur->ch[0], rank);
    else if (rank <= less_siz + cur->rep_cnt)
      return cur->val;
    else
      return _query_val(cur->ch[1], rank - less_siz - cur->rep_cnt);
  }

  int _query_prev(Node *cur, int val) {
    if (val <= cur->val) {
      if (cur->ch[0] != nullptr) return _query_prev(cur->ch[0], val);
    } else {
      q_prev_tmp = cur->val;
      if (cur->ch[1] != nullptr) _query_prev(cur->ch[1], val);
      return q_prev_tmp;
    }
    return -1145;
  }

  int _query_nex(Node *cur, int val) {
    if (val >= cur->val) {
      if (cur->ch[1] != nullptr) return _query_nex(cur->ch[1], val);
    } else {
      q_nex_tmp = cur->val;
      if (cur->ch[0] != nullptr) _query_nex(cur->ch[0], val);
      return q_nex_tmp;
    }
    return -1145;
  }

 public:
  void insert(int val) { _insert(root, val); }

  void del(int val) { _del(root, val); }

  int query_rank(int val) { return _query_rank(root, val); }

  int query_val(int rank) { return _query_val(root, rank); }

  int query_prev(int val) { return _query_prev(root, val); }

  int query_nex(int val) { return _query_nex(root, val); }
};

Treap tr;

int main() {
  srand(0);
  int t;
  scanf("%d", &t);
  while (t--) {
    int mode;
    int num;
    scanf("%d%d", &mode, &num);
    switch (mode) {
      case 1:
        tr.insert(num);
        break;
      case 2:
        tr.del(num);
        break;
      case 3:
        printf("%d\n", tr.query_rank(num));
        break;
      case 4:
        printf("%d\n", tr.query_val(num));
        break;
      case 5:
        printf("%d\n", tr.query_prev(num));
        break;
      case 6:
        printf("%d\n", tr.query_nex(num));
        break;
    }
  }
}

數組實現

以下是 bzoj 普通平衡樹模板代碼，使用數組實現。

完整代碼 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
#include <algorithm>
#include <cstdio>
#include <iostream>

#define maxn 100005
#define INF (1 << 30)

int n;

struct treap {  // 直接维护成数据结构，可以直接用
  int l[maxn], r[maxn], val[maxn], rnd[maxn], size_[maxn], w[maxn];
  int sz, ans, rt;

  void pushup(int x) { size_[x] = size_[l[x]] + size_[r[x]] + w[x]; }

  void lrotate(int &k) {
    int t = r[k];
    r[k] = l[t];
    l[t] = k;
    size_[t] = size_[k];
    pushup(k);
    k = t;
  }

  void rrotate(int &k) {
    int t = l[k];
    l[k] = r[t];
    r[t] = k;
    size_[t] = size_[k];
    pushup(k);
    k = t;
  }

  void insert(int &k, int x) {  // 插入
    if (!k) {
      sz++;
      k = sz;
      size_[k] = 1;
      w[k] = 1;
      val[k] = x;
      rnd[k] = rand();
      return;
    }
    size_[k]++;
    if (val[k] == x) {
      w[k]++;
    } else if (val[k] < x) {
      insert(r[k], x);
      if (rnd[r[k]] < rnd[k]) lrotate(k);
    } else {
      insert(l[k], x);
      if (rnd[l[k]] < rnd[k]) rrotate(k);
    }
  }

  bool del(int &k, int x) {  // 删除节点
    if (!k) return false;
    if (val[k] == x) {
      if (w[k] > 1) {
        w[k]--;
        size_[k]--;
        return true;
      }
      if (l[k] == 0 || r[k] == 0) {
        k = l[k] + r[k];
        return true;
      } else if (rnd[l[k]] < rnd[r[k]]) {
        rrotate(k);
        return del(k, x);
      } else {
        lrotate(k);
        return del(k, x);
      }
    } else if (val[k] < x) {
      bool succ = del(r[k], x);
      if (succ) size_[k]--;
      return succ;
    } else {
      bool succ = del(l[k], x);
      if (succ) size_[k]--;
      return succ;
    }
  }

  int queryrank(int k, int x) {
    if (!k) return 0;
    if (val[k] == x)
      return size_[l[k]] + 1;
    else if (x > val[k]) {
      return size_[l[k]] + w[k] + queryrank(r[k], x);
    } else
      return queryrank(l[k], x);
  }

  int querynum(int k, int x) {
    if (!k) return 0;
    if (x <= size_[l[k]])
      return querynum(l[k], x);
    else if (x > size_[l[k]] + w[k])
      return querynum(r[k], x - size_[l[k]] - w[k]);
    else
      return val[k];
  }

  void querypre(int k, int x) {
    if (!k) return;
    if (val[k] < x)
      ans = k, querypre(r[k], x);
    else
      querypre(l[k], x);
  }

  void querysub(int k, int x) {
    if (!k) return;
    if (val[k] > x)
      ans = k, querysub(l[k], x);
    else
      querysub(r[k], x);
  }
} T;

int main() {
  srand(123);
  scanf("%d", &n);
  int opt, x;
  for (int i = 1; i <= n; i++) {
    scanf("%d%d", &opt, &x);
    if (opt == 1)
      T.insert(T.rt, x);
    else if (opt == 2)
      T.del(T.rt, x);
    else if (opt == 3) {
      printf("%d\n", T.queryrank(T.rt, x));
    } else if (opt == 4) {
      printf("%d\n", T.querynum(T.rt, x));
    } else if (opt == 5) {
      T.ans = 0;
      T.querypre(T.rt, x);
      printf("%d\n", T.val[T.ans]);
    } else if (opt == 6) {
      T.ans = 0;
      T.querysub(T.rt, x);
      printf("%d\n", T.val[T.ans]);
    }
  }
  return 0;
}

無旋 treap

指針實現

完整代碼

以下是前文講解的代碼的完整版本，是普通平衡樹的模板代碼。

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
// author: (ttzytt)[ttzytt.com]
#include <bits/stdc++.h>
using namespace std;

struct Node {
  Node *ch[2];
  int val, prio;
  int cnt;
  int siz;

  Node(int _val) : val(_val), cnt(1), siz(1) {
    ch[0] = ch[1] = nullptr;
    prio = rand();
  }

  Node(Node *_node) {
    val = _node->val, prio = _node->prio, cnt = _node->cnt, siz = _node->siz;
  }

  void upd_siz() {
    siz = cnt;
    if (ch[0] != nullptr) siz += ch[0]->siz;
    if (ch[1] != nullptr) siz += ch[1]->siz;
  }
};

struct none_rot_treap {
#define _3 second.second
#define _2 second.first
  Node *root;

  pair<Node *, Node *> split(Node *cur, int key) {
    if (cur == nullptr) return {nullptr, nullptr};
    if (cur->val <= key) {
      auto temp = split(cur->ch[1], key);
      cur->ch[1] = temp.first;
      cur->upd_siz();
      return {cur, temp.second};
    } else {
      auto temp = split(cur->ch[0], key);
      cur->ch[0] = temp.second;
      cur->upd_siz();
      return {temp.first, cur};
    }
  }

  tuple<Node *, Node *, Node *> split_by_rk(Node *cur, int rk) {
    if (cur == nullptr) return {nullptr, nullptr, nullptr};
    int ls_siz = cur->ch[0] == nullptr ? 0 : cur->ch[0]->siz;
    if (rk <= ls_siz) {
      Node *l, *mid, *r;
      tie(l, mid, r) = split_by_rk(cur->ch[0], rk);
      cur->ch[0] = r;
      cur->upd_siz();
      return {l, mid, cur};
    } else if (rk <= ls_siz + cur->cnt) {
      Node *lt = cur->ch[0];
      Node *rt = cur->ch[1];
      cur->ch[0] = cur->ch[1] = nullptr;
      return {lt, cur, rt};
    } else {
      Node *l, *mid, *r;
      tie(l, mid, r) = split_by_rk(cur->ch[1], rk - ls_siz - cur->cnt);
      cur->ch[1] = l;
      cur->upd_siz();
      return {cur, mid, r};
    }
  }

  Node *merge(Node *u, Node *v) {
    if (u == nullptr && v == nullptr) return nullptr;
    if (u != nullptr && v == nullptr) return u;
    if (v != nullptr && u == nullptr) return v;
    if (u->prio < v->prio) {
      u->ch[1] = merge(u->ch[1], v);
      u->upd_siz();
      return u;
    } else {
      v->ch[0] = merge(u, v->ch[0]);
      v->upd_siz();
      return v;
    }
  }

  void insert(int val) {
    auto temp = split(root, val);
    auto l_tr = split(temp.first, val - 1);
    Node *new_node;
    if (l_tr.second == nullptr) {
      new_node = new Node(val);
    } else {
      l_tr.second->cnt++;
      l_tr.second->upd_siz();
    }
    Node *l_tr_combined =
        merge(l_tr.first, l_tr.second == nullptr ? new_node : l_tr.second);
    root = merge(l_tr_combined, temp.second);
  }

  void del(int val) {
    auto temp = split(root, val);
    auto l_tr = split(temp.first, val - 1);
    if (l_tr.second->cnt > 1) {
      l_tr.second->cnt--;
      l_tr.second->upd_siz();
      l_tr.first = merge(l_tr.first, l_tr.second);
    } else {
      if (temp.first == l_tr.second) {
        temp.first = nullptr;
      }
      delete l_tr.second;
      l_tr.second = nullptr;
    }
    root = merge(l_tr.first, temp.second);
  }

  int qrank_by_val(Node *cur, int val) {
    auto temp = split(cur, val - 1);
    int ret = (temp.first == nullptr ? 0 : temp.first->siz) + 1;
    root = merge(temp.first, temp.second);
    return ret;
  }

  int qval_by_rank(Node *cur, int rk) {
    Node *l, *mid, *r;
    tie(l, mid, r) = split_by_rk(cur, rk);
    int ret = mid->val;
    root = merge(merge(l, mid), r);
    return ret;
  }

  int qprev(int val) {
    auto temp = split(root, val - 1);
    int ret = qval_by_rank(temp.first, temp.first->siz);
    root = merge(temp.first, temp.second);
    return ret;
  }

  int qnex(int val) {
    auto temp = split(root, val);
    int ret = qval_by_rank(temp.second, 1);
    root = merge(temp.first, temp.second);
    return ret;
  }
};

none_rot_treap tr;

int main() {
  srand(time(0));
  int t;
  scanf("%d", &t);
  while (t--) {
    int mode;
    int num;
    scanf("%d%d", &mode, &num);
    switch (mode) {
      case 1:
        tr.insert(num);
        break;
      case 2:
        tr.del(num);
        break;
      case 3:
        printf("%d\n", tr.qrank_by_val(tr.root, num));
        break;
      case 4:
        printf("%d\n", tr.qval_by_rank(tr.root, num));
        break;
      case 5:
        printf("%d\n", tr.qprev(num));
        break;
      case 6:
        printf("%d\n", tr.qnex(num));
        break;
    }
  }
}

無旋 treap 的區間操作

指針實現

完整代碼

以下是前文講解的代碼的完整版本，是文藝平衡樹題目的模板代碼。

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
// author: (ttzytt)[ttzytt.com]
#include <bits/stdc++.h>
using namespace std;

// 參考：https://www.cnblogs.com/Equinox-Flower/p/10785292.html
struct Node {
  Node* ch[2];
  int val, prio;
  int cnt;
  int siz;
  bool to_rev = false;  // 需要把這個子樹下的每一個節點都翻轉過來

  Node(int _val) : val(_val), cnt(1), siz(1) {
    ch[0] = ch[1] = nullptr;
    prio = rand();
  }

  int upd_siz() {
    siz = cnt;
    if (ch[0] != nullptr) siz += ch[0]->siz;
    if (ch[1] != nullptr) siz += ch[1]->siz;
    return siz;
  }

  void pushdown() {
    swap(ch[0], ch[1]);
    if (ch[0] != nullptr) ch[0]->to_rev ^= 1;
    // 如果原來子節點也要翻轉，那兩次翻轉就抵消了，如果子節點不翻轉，那這個
    //  tag 就需要繼續被 push 到子節點上
    if (ch[1] != nullptr) ch[1]->to_rev ^= 1;
    to_rev = false;
  }

  void check_tag() {
    if (to_rev) pushdown();
  }
};

struct Seg_treap {
  Node* root;
#define siz(_) (_ == nullptr ? 0 : _->siz)

  pair<Node*, Node*> split(Node* cur, int sz) {
    // 按照樹的大小劃分
    if (cur == nullptr) return {nullptr, nullptr};
    cur->check_tag();
    if (sz <= siz(cur->ch[0])) {
      // 左邊的子樹就夠了
      auto temp = split(cur->ch[0], sz);
      // 左邊的子樹不一定全部需要，temp.second 是不需要的
      cur->ch[0] = temp.second;
      cur->upd_siz();
      return {temp.first, cur};
    } else {
      // 左邊的加上右邊的一部分（當然也包括這個節點本身）
      auto temp = split(cur->ch[1], sz - siz(cur->ch[0]) - 1);
      cur->ch[1] = temp.first;
      cur->upd_siz();
      return {cur, temp.second};
    }
  }

  Node* merge(Node* sm, Node* bg) {
    // small, big
    if (sm == nullptr && bg == nullptr) return nullptr;
    if (sm != nullptr && bg == nullptr) return sm;
    if (sm == nullptr && bg != nullptr) return bg;
    sm->check_tag(), bg->check_tag();
    if (sm->prio < bg->prio) {
      sm->ch[1] = merge(sm->ch[1], bg);
      sm->upd_siz();
      return sm;
    } else {
      bg->ch[0] = merge(sm, bg->ch[0]);
      bg->upd_siz();
      return bg;
    }
  }

  void insert(int val) {
    auto temp = split(root, val);
    auto l_tr = split(temp.first, val - 1);
    Node* new_node;
    if (l_tr.second == nullptr) new_node = new Node(val);
    Node* l_tr_combined =
        merge(l_tr.first, l_tr.second == nullptr ? new_node : l_tr.second);
    root = merge(l_tr_combined, temp.second);
  }

  void seg_rev(int l, int r) {
    // 這裏的 less 和 more 是相對於 l 的
    auto less = split(root, l - 1);
    // 所有小於等於 l - 1 的會在 less 的左邊
    auto more = split(less.second, r - l + 1);
    // 拿出從 l 開始的前 r - l + 1 個
    more.first->to_rev = true;
    root = merge(less.first, merge(more.first, more.second));
  }

  void print(Node* cur) {
    if (cur == nullptr) return;
    cur->check_tag();
    print(cur->ch[0]);
    cout << cur->val << " ";
    print(cur->ch[1]);
  }
};

Seg_treap tr;

int main() {
  srand(time(0));
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= n; i++) tr.insert(i);
  while (m--) {
    int l, r;
    cin >> l >> r;
    tr.seg_rev(l, r);
  }
  tr.print(tr.root);
}

例題

普通平衡樹

文藝平衡樹（Splay）

「ZJOI2006」書架

「NOI2005」維護數列

CF 702F T-Shirts

參考資料與註釋

  1. https://ttzytt.com/2022/06/treap_note/ ↩

  2. 本圖的設計參考了 維基百科 treap 詞條的配圖 ↩

  3. https://charleswu.site/archives/1051 ↩

  4. https://www.cnblogs.com/Equinox-Flower/p/10785292.html ↩↩↩

  5. https://www.luogu.com.cn/blog/85514/fhq-treap-xue-xi-bi-ji ↩

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：Dev-XYS, ttzytt, Sora233
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用