跳转至

Splay 樹

本頁面將簡要介紹如何用 Splay 維護二叉查找樹。

定義

Splay 樹, 或 伸展樹，是一種平衡二叉查找樹，它通過 Splay/伸展操作 不斷將某個節點旋轉到根節點，使得整棵樹仍然滿足二叉查找樹的性質，能夠在均攤 \(O(\log N)\) 時間內完成插入，查找和刪除操作，並且保持平衡而不至於退化為鏈。

Splay 樹由 Daniel Sleator 和 Robert Tarjan 於 1985 年發明。

結構

二叉查找樹的性質

Splay 樹是一棵二叉搜索樹，查找某個值時滿足性質：左子樹任意節點的值 \(<\) 根節點的值 \(<\) 右子樹任意節點的值。

節點維護信息

rt tot fa[i] ch[i][0/1] val[i] cnt[i] sz[i]
根節點編號 節點個數 父親 左右兒子編號 節點權值 權值出現次數 子樹大小

操作

基本操作

  • maintain(x)：在改變節點位置後，將節點 \(x\) 的 \(\text{size}\) 更新。
  • get(x)：判斷節點 \(x\) 是父親節點的左兒子還是右兒子。
  • clear(x)：銷燬節點 \(x\)。
實現 
1
2
3
4
5
void maintain(int x) { sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + cnt[x]; }

bool get(int x) { return x == ch[fa[x]][1]; }

void clear(int x) { ch[x][0] = ch[x][1] = fa[x] = val[x] = sz[x] = cnt[x] = 0; }

旋轉操作

為了使 Splay 保持平衡而進行旋轉操作，旋轉的本質是將某個節點上移一個位置。

旋轉需要保證：

  • 整棵 Splay 的中序遍歷不變（不能破壞二叉查找樹的性質）。
  • 受影響的節點維護的信息依然正確有效。
  • root 必須指向旋轉後的根節點。

在 Splay 中旋轉分為兩種：左旋和右旋。

過程

具體分析旋轉步驟（假設需要旋轉的節點為 \(x\)，其父親為 \(y\)，以右旋為例）

  1. 將 \(y\) 的左兒子指向 \(x\) 的右兒子，且 \(x\) 的右兒子（如果 \(x\) 有右兒子的話）的父親指向 \(y\)；ch[y][0]=ch[x][1]; fa[ch[x][1]]=y;
  2. 將 \(x\) 的右兒子指向 \(y\)，且 \(y\) 的父親指向 \(x\)；ch[x][chk^1]=y; fa[y]=x;
  3. 如果原來的 \(y\) 還有父親 \(z\)，那麼把 \(z\) 的某個兒子（原來 \(y\) 所在的兒子位置）指向 \(x\)，且 \(x\) 的父親指向 \(z\)。fa[x]=z; if(z) ch[z][y==ch[z][1]]=x;

實現

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
void rotate(int x) {
  int y = fa[x], z = fa[y], chk = get(x);
  ch[y][chk] = ch[x][chk ^ 1];
  if (ch[x][chk ^ 1]) fa[ch[x][chk ^ 1]] = y;
  ch[x][chk ^ 1] = y;
  fa[y] = x;
  fa[x] = z;
  if (z) ch[z][y == ch[z][1]] = x;
  maintain(y);
  maintain(x);
}

Splay 操作

Splay 操作規定：每訪問一個節點 \(x\) 後都要強制將其旋轉到根節點。

Splay 操作即對 \(x\) 做一系列的 splay 步驟。每次對 \(x\) 做一次 splay 步驟，\(x\) 到根節點的距離都會更近。定義 \(p\) 為 \(x\) 的父節點。Splay 步驟有三種，具體分為六種情況：

  1. zig: 在 \(p\) 是根節點時操作。Splay 樹會根據 \(x\) 和 \(p\) 間的邊旋轉。\(zig\) 存在是用於處理奇偶校驗問題，僅當 \(x\) 在 splay 操作開始時具有奇數深度時作為 splay 操作的最後一步執行。

    splay-zig

    即直接將 \(x\) 左旋或右旋（圖 1, 2）

    圖 1

    圖 2

  2. zig-zig: 在 \(p\) 不是根節點且 \(x\) 和 \(p\) 都是右側子節點或都是左側子節點時操作。下方例圖顯示了 \(x\) 和 \(p\) 都是左側子節點時的情況。Splay 樹首先按照連接 \(p\) 與其父節點 \(g\) 邊旋轉，然後按照連接 \(x\) 和 \(p\) 的邊旋轉。

    splay-zig-zig

    即首先將 \(g\) 左旋或右旋，然後將 \(x\) 右旋或左旋（圖 3, 4）。

    圖 3

    圖 4

  3. zig-zag: 在 \(p\) 不是根節點且 \(x\) 和 \(p\) 一個是右側子節點一個是左側子節點時操作。Splay 樹首先按 \(p\) 和 \(x\) 之間的邊旋轉，然後按 \(x\) 和 \(g\) 新生成的結果邊旋轉。

    splay-zig-zag

    即將 \(x\) 先左旋再右旋、或先右旋再左旋（圖 5, 6）。

    圖 5

    圖 6

    Tip

    請讀者嘗試自行模擬 \(6\) 種旋轉情況，以理解 Splay 的基本思想。

實現

1
2
3
4
5
void splay(int x) {
  for (int f = fa[x]; f = fa[x], f; rotate(x))
    if (fa[f]) rotate(get(x) == get(f) ? f : x);
  rt = x;
}

Splay 操作的時間複雜度

因為 zig 和 zag 是 對稱 操作，我們只需要對 zig，zig−zig，zig−zag 操作分析複雜度。採用 勢能分析，定義一個 \(n\) 個節點的 splay 樹進行了 \(m\) 次 splay 步驟。可記 \(w(x)=[\log(\operatorname{size}(x))]\), 定義勢能函數為 \(\varphi =\sum w(x)\),\(\varphi (0) \leq n \log n\)，在第 \(i\) 次操作後勢能為 \(\varphi (i)\), 則我們只需要求出初始勢能和每次的勢能變化量的和即可。

  1. zig: 勢能的變化量為

    \[ \begin{aligned} 1+w'(x)+w'(fa)−w(x)−w(fa) & \leq 1+w'(fa)−w(x) \\ & \leq 1+w'(x)−w(x) \end{aligned} \]

  2. zig-zig: 勢能變化量為

    \[ \begin{aligned} 1+w'(x)+w'(fa)+w'(g)−w(x)−w(fa)−w(g) & \leq 1+w'(fa)+w'(g)−w(x)−w(fa) \\ & \leq 1+ w'(x)+w'(g)−2w(x) \\ & \leq 3(w'(x)−w(x)) \end{aligned} \]

  3. zig-zag: 勢能變化量為

    \[ \begin{aligned} 1+w'(x)+w'(fa)+w'(g)−w(x)−w(fa)−w(g) & \leq 1+w'(fa)+w'(g)−w(x)−w(fa) \\ & \leq 1+w'(g)+w'(fa)−2w(x) \\ & \leq 2 w'(x)−w'(g)−w'(fa) + w'(fa)+w'(g)−w(x)−w(fa) \\ & \leq 2(w'(x)−w(x)) \end{aligned} \]

由此可見，三種 splay 步驟的勢能全部可以縮放為 \(\leq 3(w'(x)−w(x))\). 令 \(w^{(n)}(x)=w'^{(n-1)}(x)\),\(w^{(0)}(x)=w(x)\), 假設 splay 操作一次依次訪問了 \(x_{1}, x_{2}, \cdots, x_{n}\), 最終 \(x_{1}\) 成為根節點，我們可以得到：

\[ \begin{aligned} 3\left(\sum_{i=0}^{n-2}\left(w^{(i+1)}(x_{1})-w^{(i)}(x_{1})\right)+w(n)−w^{(n-1)}(x_{1})\right)+1 & = 3(w(n)−w(x_{1}))+1 \\ & \leq \log n \end{aligned} \]

繼而可得：

\[ \sum_{i=1}^m (\varphi (m-i+1)−\varphi (m−i)) +\varphi (0) = n \log n+m \log n \]

因此，對於 \(n\) 個節點的 splay 樹，做一次 splay 操作的均攤複雜度為 \(O(\log n)\)。因此基於 splay 的插入，查詢，刪除等操作的時間複雜度也為均攤 \(O(\log n)\)。

插入操作

過程

插入操作是一個比較複雜的過程，具體步驟如下（假設插入的值為 \(k\)）：

  • 如果樹空了，則直接插入根並退出。
  • 如果當前節點的權值等於 \(k\) 則增加當前節點的大小並更新節點和父親的信息，將當前節點進行 Splay 操作。
  • 否則按照二叉查找樹的性質向下找，找到空節點就插入即可（請不要忘記 Splay 操作）。

實現

 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
void ins(int k) {
  if (!rt) {
    val[++tot] = k;
    cnt[tot]++;
    rt = tot;
    maintain(rt);
    return;
  }
  int cur = rt, f = 0;
  while (1) {
    if (val[cur] == k) {
      cnt[cur]++;
      maintain(cur);
      maintain(f);
      splay(cur);
      break;
    }
    f = cur;
    cur = ch[cur][val[cur] < k];
    if (!cur) {
      val[++tot] = k;
      cnt[tot]++;
      fa[tot] = f;
      ch[f][val[f] < k] = tot;
      maintain(tot);
      maintain(f);
      splay(tot);
      break;
    }
  }
}

查詢 x 的排名

過程

根據二叉查找樹的定義和性質，顯然可以按照以下步驟查詢 \(x\) 的排名：

  • 如果 \(x\) 比當前節點的權值小，向其左子樹查找。
  • 如果 \(x\) 比當前節點的權值大，將答案加上左子樹（\(size\)）和當前節點（\(cnt\)）的大小，向其右子樹查找。
  • 如果 \(x\) 與當前節點的權值相同，將答案加 \(1\) 並返回。

注意最後需要進行 Splay 操作。

實現

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
int rk(int k) {
  int res = 0, cur = rt;
  while (1) {
    if (k < val[cur]) {
      cur = ch[cur][0];
    } else {
      res += sz[ch[cur][0]];
      if (k == val[cur]) {
        splay(cur);
        return res + 1;
      }
      res += cnt[cur];
      cur = ch[cur][1];
    }
  }
}

查詢排名 x 的數

過程

設 \(k\) 為剩餘排名，具體步驟如下：

  • 如果左子樹非空且剩餘排名 \(k\) 不大於左子樹的大小 \(size\)，那麼向左子樹查找。
  • 否則將 \(k\) 減去左子樹的和根的大小。如果此時 \(k\) 的值小於等於 \(0\)，則返回根節點的權值，否則繼續向右子樹查找。

實現

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
int kth(int k) {
  int cur = rt;
  while (1) {
    if (ch[cur][0] && k <= sz[ch[cur][0]]) {
      cur = ch[cur][0];
    } else {
      k -= cnt[cur] + sz[ch[cur][0]];
      if (k <= 0) {
        splay(cur);
        return val[cur];
      }
      cur = ch[cur][1];
    }
  }
}

查詢前驅

過程

前驅定義為小於 \(x\) 的最大的數，那麼查詢前驅可以轉化為：將 \(x\) 插入（此時 \(x\) 已經在根的位置了），前驅即為 \(x\) 的左子樹中最右邊的節點，最後將 \(x\) 刪除即可。

實現

1
2
3
4
5
6
7
int pre() {
  int cur = ch[rt][0];
  if (!cur) return cur;
  while (ch[cur][1]) cur = ch[cur][1];
  splay(cur);
  return cur;
}

查詢後繼

過程

後繼定義為大於 \(x\) 的最小的數，查詢方法和前驅類似：\(x\) 的右子樹中最左邊的節點。

實現

1
2
3
4
5
6
7
int nxt() {
  int cur = ch[rt][1];
  if (!cur) return cur;
  while (ch[cur][0]) cur = ch[cur][0];
  splay(cur);
  return cur;
}

合併兩棵樹

過程

合併兩棵 Splay 樹，設兩棵樹的根節點分別為 \(x\) 和 \(y\)，那麼我們要求 \(x\) 樹中的最大值小於 \(y\) 樹中的最小值。合併操作如下：

  • 如果 \(x\) 和 \(y\) 其中之一或兩者都為空樹，直接返回不為空的那一棵樹的根節點或空樹。
  • 否則將 \(x\) 樹中的最大值 \(\operatorname{Splay}\) 到根，然後把它的右子樹設置為 \(y\) 並更新節點的信息，然後返回這個節點。

刪除操作

過程

刪除操作也是一個比較複雜的操作，具體步驟如下：

首先將 \(x\) 旋轉到根的位置。

  • 如果 \(cnt[x]>1\)（有不止一個 \(x\)），那麼將 \(cnt[x]\) 減 \(1\) 並退出。
  • 否則，合併它的左右兩棵子樹即可。

實現

 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
void del(int k) {
  rk(k);
  if (cnt[rt] > 1) {
    cnt[rt]--;
    maintain(rt);
    return;
  }
  if (!ch[rt][0] && !ch[rt][1]) {
    clear(rt);
    rt = 0;
    return;
  }
  if (!ch[rt][0]) {
    int cur = rt;
    rt = ch[rt][1];
    fa[rt] = 0;
    clear(cur);
    return;
  }
  if (!ch[rt][1]) {
    int cur = rt;
    rt = ch[rt][0];
    fa[rt] = 0;
    clear(cur);
    return;
  }
  int cur = rt, x = pre();
  fa[ch[cur][1]] = x;
  ch[x][1] = ch[cur][1];
  clear(cur);
  maintain(rt);
}

實現

  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
#include <cstdio>
const int N = 100005;
int rt, tot, fa[N], ch[N][2], val[N], cnt[N], sz[N];

struct Splay {
  void maintain(int x) { sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + cnt[x]; }

  bool get(int x) { return x == ch[fa[x]][1]; }

  void clear(int x) {
    ch[x][0] = ch[x][1] = fa[x] = val[x] = sz[x] = cnt[x] = 0;
  }

  void rotate(int x) {
    int y = fa[x], z = fa[y], chk = get(x);
    ch[y][chk] = ch[x][chk ^ 1];
    if (ch[x][chk ^ 1]) fa[ch[x][chk ^ 1]] = y;
    ch[x][chk ^ 1] = y;
    fa[y] = x;
    fa[x] = z;
    if (z) ch[z][y == ch[z][1]] = x;
    maintain(y);
    maintain(x);
  }

  void splay(int x) {
    for (int f = fa[x]; f = fa[x], f; rotate(x))
      if (fa[f]) rotate(get(x) == get(f) ? f : x);
    rt = x;
  }

  void ins(int k) {
    if (!rt) {
      val[++tot] = k;
      cnt[tot]++;
      rt = tot;
      maintain(rt);
      return;
    }
    int cur = rt, f = 0;
    while (1) {
      if (val[cur] == k) {
        cnt[cur]++;
        maintain(cur);
        maintain(f);
        splay(cur);
        break;
      }
      f = cur;
      cur = ch[cur][val[cur] < k];
      if (!cur) {
        val[++tot] = k;
        cnt[tot]++;
        fa[tot] = f;
        ch[f][val[f] < k] = tot;
        maintain(tot);
        maintain(f);
        splay(tot);
        break;
      }
    }
  }

  int rk(int k) {
    int res = 0, cur = rt;
    while (1) {
      if (k < val[cur]) {
        cur = ch[cur][0];
      } else {
        res += sz[ch[cur][0]];
        if (k == val[cur]) {
          splay(cur);
          return res + 1;
        }
        res += cnt[cur];
        cur = ch[cur][1];
      }
    }
  }

  int kth(int k) {
    int cur = rt;
    while (1) {
      if (ch[cur][0] && k <= sz[ch[cur][0]]) {
        cur = ch[cur][0];
      } else {
        k -= cnt[cur] + sz[ch[cur][0]];
        if (k <= 0) {
          splay(cur);
          return val[cur];
        }
        cur = ch[cur][1];
      }
    }
  }

  int pre() {
    int cur = ch[rt][0];
    if (!cur) return cur;
    while (ch[cur][1]) cur = ch[cur][1];
    splay(cur);
    return cur;
  }

  int nxt() {
    int cur = ch[rt][1];
    if (!cur) return cur;
    while (ch[cur][0]) cur = ch[cur][0];
    splay(cur);
    return cur;
  }

  void del(int k) {
    rk(k);
    if (cnt[rt] > 1) {
      cnt[rt]--;
      maintain(rt);
      return;
    }
    if (!ch[rt][0] && !ch[rt][1]) {
      clear(rt);
      rt = 0;
      return;
    }
    if (!ch[rt][0]) {
      int cur = rt;
      rt = ch[rt][1];
      fa[rt] = 0;
      clear(cur);
      return;
    }
    if (!ch[rt][1]) {
      int cur = rt;
      rt = ch[rt][0];
      fa[rt] = 0;
      clear(cur);
      return;
    }
    int cur = rt;
    int x = pre();
    fa[ch[cur][1]] = x;
    ch[x][1] = ch[cur][1];
    clear(cur);
    maintain(rt);
  }
} tree;

int main() {
  int n, opt, x;
  for (scanf("%d", &n); n; --n) {
    scanf("%d%d", &opt, &x);
    if (opt == 1)
      tree.ins(x);
    else if (opt == 2)
      tree.del(x);
    else if (opt == 3)
      printf("%d\n", tree.rk(x));
    else if (opt == 4)
      printf("%d\n", tree.kth(x));
    else if (opt == 5)
      tree.ins(x), printf("%d\n", val[tree.pre()]), tree.del(x);
    else
      tree.ins(x), printf("%d\n", val[tree.nxt()]), tree.del(x);
  }
  return 0;
}

序列操作

Splay 也可以運用在序列上，用於維護區間信息。與線段樹對比，Splay 常數較大，但是支持更復雜的序列操作，如區間翻轉等。

將序列建成的 Splay 有如下性質：

  • Splay 的中序遍歷相當於原序列從左到右的遍歷。

  • Splay 上的一個節點代表原序列的一個元素；Splay 上的一顆子樹，代表原序列的一段區間。

因為有 splay 操作，可以快速提取出代表某個區間的 Splay 子樹。

在操作之前，你需要先把這顆 Splay 建出來。根據 Splay 的特性，直接建出一顆只有右兒子的鏈即可，時間複雜度仍然是正確的。

一些進階操作

Splay 的一顆子樹代表原序列的一段區間。現在想找到序列區間 \([L, R]\) 代表的子樹，只需要將代表 \(a_{L - 1}\) 的節點 Splay 到根，再將代表 \(a_{R + 1}\) 的節點 splay 到根的右兒子即可。根據「Splay 的中序遍歷相當於原序列從左到右的遍歷」，對應 \(a_{R + 1}\) 的節點的左子樹中序遍歷為序列 \(a[L, R]\)，故其為區間 \([L, R]\) 代表的子樹。

一般會建立左右兩個哨兵節點 \(0\) 和 \(n + 1\)，放在數列的最開頭和最結尾，防止 \(L - 1\) 或 \(R + 1\) 超出數列範圍。

所以要將 splay 函數進行一些修改，能夠實現將節點旋轉到目標點的兒子。如果目標點 goal 為 \(0\) 説明旋轉到根節點。

實現

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
void splay(int x, int goal = 0) {
  if (goal == 0) rt = x;
  while (fa[x] != goal) {
    int f = fa[x], g = fa[fa[x]];
    if (g != goal) {
      if (get(f) == get(x))
        rotate(x);
      else
        rotate(f);
    }
    rotate(x);
  }
}

區間翻轉

Splay 常見的應用之一，模板題目是 文藝平衡樹。

過程

先將詢問區間的子樹提取出來。因為是區間翻轉，我們需要將這顆子樹的中序遍歷順序翻轉。

一個暴力做法是每次將根節點的左右兒子交換，然後遞歸左右子樹做同樣的操作，這樣複雜度為 \(O(n)\)，不可承受。可以考慮使用懶標記，先給根打上「翻轉標記」並交換其左右兒子。當遞歸到一個帶懶標記的點時，將懶標記下傳即可。

實現

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
void tagrev(int x) {
  swap(ch[x][0], ch[x][1]);
  lazy[x] ^= 1;
}

void pushdown(int x) {
  if (lazy[x]) {
    tagrev(ch[x][0]);
    tagrev(ch[x][1]);
    lazy[x] = 0;
  }
}

void reverse(int l, int r) {
  int L = kth(l - 1), R = kth(r + 1);
  splay(L), splay(R, L);
  int tmp = ch[ch[L][1]][0];
  tagrev(tmp);
}

實現

注意 \(\operatorname{kth}\) 中要下傳翻轉標記。

  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
#include <algorithm>
#include <cstdio>
const int N = 100005;

int n, m, l, r, a[N];

int rt, tot, fa[N], ch[N][2], val[N], sz[N], lazy[N];

struct Splay {
  void maintain(int x) { sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + 1; }

  bool get(int x) { return x == ch[fa[x]][1]; }

  void clear(int x) {
    ch[x][0] = ch[x][1] = fa[x] = val[x] = sz[x] = lazy[x] = 0;
  }

  void rotate(int x) {
    int y = fa[x], z = fa[y], chk = get(x);
    ch[y][chk] = ch[x][chk ^ 1];
    if (ch[x][chk ^ 1]) fa[ch[x][chk ^ 1]] = y;
    ch[x][chk ^ 1] = y;
    fa[y] = x;
    fa[x] = z;
    if (z) ch[z][y == ch[z][1]] = x;
    maintain(y);
    maintain(x);
  }

  void splay(int x, int goal = 0) {
    if (goal == 0) rt = x;
    while (fa[x] != goal) {
      int f = fa[x], g = fa[fa[x]];
      if (g != goal) {
        if (get(f) == get(x))
          rotate(x);
        else
          rotate(f);
      }
      rotate(x);
    }
  }

  void tagrev(int x) {
    std::swap(ch[x][0], ch[x][1]);
    lazy[x] ^= 1;
  }

  void pushdown(int x) {
    if (lazy[x]) {
      tagrev(ch[x][0]);
      tagrev(ch[x][1]);
      lazy[x] = 0;
    }
  }

  int build(int l, int r, int f) {
    if (l > r) return 0;
    int mid = (l + r) / 2, cur = ++tot;
    val[cur] = a[mid], fa[cur] = f;
    ch[cur][0] = build(l, mid - 1, cur);
    ch[cur][1] = build(mid + 1, r, cur);
    maintain(cur);
    return cur;
  }

  int kth(int k) {
    int cur = rt;
    while (1) {
      pushdown(cur);
      if (ch[cur][0] && k <= sz[ch[cur][0]]) {
        cur = ch[cur][0];
      } else {
        k -= 1 + sz[ch[cur][0]];
        if (k <= 0) {
          splay(cur);
          return cur;
        }
        cur = ch[cur][1];
      }
    }
  }

  void reverse(int l, int r) {
    int L = kth(l), R = kth(r + 2);
    splay(L), splay(R, L);
    int tmp = ch[ch[L][1]][0];
    tagrev(tmp);
  }

  void print(int x) {
    pushdown(x);
    if (ch[x][0]) print(ch[x][0]);
    if (val[x] >= 1 && val[x] <= n) printf("%d ", val[x]);
    if (ch[x][1]) print(ch[x][1]);
  }
} tree;

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i <= n + 1; i++) a[i] = i;
  rt = tree.build(0, n + 1, 0);
  while (m--) {
    scanf("%d%d", &l, &r);
    tree.reverse(l, r);
  }
  tree.print(rt);
  return 0;
}

例題

以下題目都是裸的 Splay 維護二叉查找樹。

習題

參考資料與註釋

本文部分內容引用於 algocode 算法博客，特別鳴謝！

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