Skip to content

Splay Tree

This page briefly introduces how to maintain a binary search tree using Splay.

Definition

Splay Tree, or Splay Tree, is a balanced binary search tree. It continuously rotates a node to the root through splay operations, ensuring the tree still satisfies the properties of a binary search tree. It can perform insertion, search, and deletion operations in amortized \(O(\log N)\) time while maintaining balance and avoiding degeneration into a chain.

The Splay tree was invented by Daniel Sleator and Robert Tarjan in 1985.

Basic Structure and Operations

This section discusses the basic structure of the Splay tree and its core operations, with the most important being the splay operation.

A Splay tree is a binary search tree. When searching for a value, it satisfies the property: the value of any node in the left subtree \(<\) the value of the root node \(<\) the value of any node in the right subtree.

Maintaining Information

This article uses arrays to simulate pointers to implement the Splay tree. The following information needs to be maintained:

rt id fa[i] ch[i][0/1] val[i] cnt[i] sz[i]
Root node ID Number of used nodes Parent Left/right child IDs Node weight Weight occurrence count Subtree size

During initialization, all information can be set to zero.

Auxiliary Operations

First, some simple auxiliary operations:

  • dir(x): Determines whether node \(x\) is the left or right child of its parent node.
  • push_up(x): After changing the node's position, updates node \(x\)'s information based on its children's information.
Implementation 
1
2
3
bool dir(int x) { return x == ch[fa[x]][1]; }

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

Rotation Operation

To keep the Splay tree balanced, rotation operations are needed. The purpose of rotation is to move a node up one position.

Rotation must ensure:

  • The in-order traversal of the entire Splay tree remains unchanged (the binary search tree properties are not violated).
  • The information maintained by the affected nodes remains correct and valid.
  • rt must point to the root node after rotation.

In Splay trees, rotations are divided into two types: left rotation and right rotation.

Observing the diagram, if we want to move node \(x\) (the \(1\) in left rotation and the \(2\) in right rotation) up through rotation, the direction of rotation is uniquely determined by whether the node is the left or right child of its parent. Therefore, when implementing the rotation operation, we only need to pass the node \(x\) to be moved up.

Detailed analysis of rotation steps: (Assume the node to be moved up is \(x\), taking right rotation as an example)

  1. First, record node \(x\)'s parent node \(y\), and \(y\)'s parent node \(z\) (which may be empty), and record whether \(x\) is the left or right child of \(y\).
  2. In the order from bottom to top in the tree after rotation, update \(y\)'s left child to \(x\)'s right child, \(x\)'s right child to \(y\), and if \(z\) is not empty, update \(z\)'s child to \(x\).
  3. In the same order, update the parent node of \(y\)'s current left child (if it exists) to \(y\), \(y\)'s parent node to \(x\), and \(x\)'s parent node to \(z\).
  4. Maintain node information from bottom to top.
Implementation 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
void rotate(int x) {
  int y = fa[x], z = fa[y];
  bool r = dir(x);
  ch[y][r] = ch[x][!r];
  ch[x][!r] = y;
  if (z) ch[z][dir(y)] = x;
  if (ch[y][r]) fa[ch[y][r]] = y;
  fa[y] = x;
  fa[x] = z;
  push_up(y);
  push_up(x);
}

When implementing all functions, be careful not to modify the information of node \(0\).

Splay Operation

The Splay tree requires that after accessing a node \(x\), it must be forcibly rotated to the root node. This operation is also called the splay operation.

Let the recently accessed node be \(x\). To perform a splay operation, we need to apply a series of splay steps to \(x\). Each time a splay step is applied to \(x\), the distance from \(x\) to the root node becomes shorter. Define \(p\) as the parent node of \(x\). There are three types of splay steps:

  1. zig: Operates when \(p\) is the root node. The Splay tree rotates according to the edge between \(x\) and \(p\). zig exists to handle parity issues and is executed only as the last step of the splay operation when \(x\) has an odd depth at the beginning of the splay operation.

    splay-zig

    That is, directly right-rotate or left-rotate \(x\) (Figures 1, 2).

    Figure 1Figure 2

  2. zig-zig: Operates when \(p\) is not the root node and both \(x\) and \(p\) are right children or both are left children. The example below shows the case where both \(x\) and \(p\) are left children. The Splay tree first rotates along the edge connecting \(p\) and its parent \(g\), then rotates along the edge connecting \(x\) and \(p\).

    splay-zig-zig

    That is, first right-rotate or left-rotate \(p\), then right-rotate or left-rotate \(x\) (Figures 3, 4).

    Figure 3Figure 4

  3. zig-zag: Operates when \(p\) is not the root node and one of \(x\) and \(p\) is a right child and the other is a left child. The Splay tree first rotates along the edge between \(p\) and \(x\), then rotates along the new resulting edge between \(x\) and \(g\).

    splay-zig-zag

    That is, first left-rotate then right-rotate \(x\), or first right-rotate then left-rotate \(x\) (Figures 5, 6).

    Figure 5Figure 6

Tip

Readers are encouraged to try simulating the six rotation scenarios themselves to understand the basic idea of the splay operation.

Comparing the three splay steps, the key to distinguishing which operation to use is to determine whether \(x\) is a child of the root node and whether \(x\) and its parent are on the same side relative to their respective parents.

The implementation provided here can specify any root node \(z\) and move any node \(x\) within its subtree up to \(z\):

  1. First, record the parent node \(w\) of the root node \(z\), so that we can use fa[x] == w to determine if \(x\) is already at the root.
  2. Record the current parent node \(y\) of \(x\). If \(y\) and \(w\) are the same, it means \(x\) has reached the root node.
  3. Otherwise, use fa[y] == w to determine if \(y\) is the root node. If it is, perform a zig operation to rotate \(x\). If not, use dir(x) == dir(y) to decide whether to use zig-zig or zig-zag. The former rotates \(y\) first and then \(x\), while the latter rotates \(x\) twice directly.
Implementation 
1
2
3
4
5
6
7
void splay(int& z, int x) {
  int w = fa[z];
  for (int y; (y = fa[x]) != w; rotate(x)) {
    if (fa[y] != w) rotate(dir(x) == dir(y) ? y : x);
  }
  z = x;
}

The splay operation is the core operation of the Splay tree and the key step that ensures its time complexity guarantee. Please ensure that after each downward access to a node, a splay operation is performed.

Additionally, the splay operation updates the information of all nodes on the path from the current node \(x\) to the root node \(z\) from bottom to top. It is precisely because of this that we can modify a non-root node and then move it up to the root via a splay operation to complete the update of the entire tree's information.

Time Complexity

The complexity of performing \(m\) splay operations on a Splay tree of size \(n\) is \(O((n+m)\log n)\), with an amortized single-operation complexity of \(O(\log n)\).

Complexity Proof Based on Potential Analysis

To prove this, we only need to analyze the complexity of the three operations: zig, zig-zig, and zig-zag. For this, we use potential analysis, studying the change in potential to derive the amortized complexity of the operations. Suppose we perform \(m\) splay operations on a Splay tree containing \(n\) nodes. The analysis can be done as follows:

Definitions:

  1. Potential of a single node: \(w(x) = \log(\text{size}(x))\), where \(\text{size}(x)\) represents the size of the subtree rooted at node \(x\).
  2. Potential of the entire tree: \(\varphi = \sum w(x)\), i.e., the sum of the potentials of all nodes in the tree. The initial potential satisfies \(\varphi_0 \leq n \log n\).
  3. Amortized cost of the \(i\)-th operation: \(c_i = t_i + \varphi_i - \varphi_{i-1}\), where \(t_i\) is the actual operation cost, and \(\varphi_i\) and \(\varphi_{i-1}\) are the potentials after and before the operation, respectively.

Properties:

  1. If \(p\) is the parent of \(x\), then \(w(p) \geq w(x)\), i.e., the parent's potential is not less than the child's potential.

  2. Since the subtree size of the root node remains unchanged before and after the operation, the potential of the root node does not change during the operation.

  3. If \(\text{size}(p)\ge\text{size}(x)+\text{size}(y)\), then \(2w(p) - w(x) - w(y) \geq 2\).

Proof of Property 3

According to the inequality of arithmetic and geometric means,

\[ \begin{aligned} 2w(p) - w(x) - w(y) &= \log\dfrac{\text{size}(p)^2}{\text{size}(x)\cdot\text{size}(y)} \\ &> \log\dfrac{\left(\text{size}(x)+\text{size}(y)\right)^2}{\text{size}(x)\cdot\text{size}(y)} \\ &\ge \log 4 \\ &= 2. \end{aligned} \]

Next, we perform potential analysis on the zig, zig-zig, and zig-zag operations separately. Let the potentials of node \(x\) before and after the operation be \(w(x)\) and \(w'(x)\), respectively. The node notation is consistent with the above section.

zig: According to properties 1 and 2, \(w(p) = w'(x)\), and \(w'(x) \geq w'(p)\). Thus, the amortized cost is

\[ \begin{aligned} c_i &= 1 + w'(x) + w'(p) - w(x) - w(p)\\ &= 1 + w'(p) - w(x)\\ &\leq 1 + w'(x) - w(x). \end{aligned} \]

zig-zig: According to properties 1 and 2, \(w(g) = w'(x)\), \(w'(x) \geq w'(p)\), and \(w(x) \leq w(p)\). Because

\[ \begin{aligned} \text{size}'(x) &= 3 + \text{size}(A) + \text{size}(B) + \text{size}(C) + \text{size}(D) \\ &> (1 + \text{size}(A) + \text{size}(B)) + (1 + \text{size}(C) + \text{size}(D)) \\ &= \text{size}(x) + \text{size}'(g), \end{aligned} \]

according to property 3, we have

\[ 2 w'(x) - w(x) - w'(g) \geq 2. \]

Thus, the amortized cost is

\[ \begin{aligned} c_i &= 2 + w'(x) + w'(p) + w'(g) - w(x) - w(p) - w(g) \\ &= 2 + w'(p) + w'(g) - w(x) - w(p) \\ &\le (2 w'(x) - w(x) - w'(g)) + w'(p) + w'(g) - w(x) - w(p) \\ &= 2(w'(x)-w(x)) + w'(p) - w(p) \\ &\le 3(w'(x)-w(x)). \end{aligned} \]

zig-zag: According to properties 1 and 2, \(w(g) = w'(x)\), and \(w(p) \geq w(x)\). Because \(\text{size}'(x)>\text{size}'(p)+\text{size}'(g)\), according to property 3, we have

\[ 2 \cdot w'(x) - w'(g) - w'(p) \geq 2. \]

Thus, the amortized cost is

\[ \begin{aligned} c_i &= 2 + w'(x) + w'(p) + w'(g) - w(x) - w(p) - w(g) \\ &= 2 + w'(p) + w'(g) - w(x) - w(p) \\ &\le (2w'(x) - w'(g) - w'(p)) + w'(p) + w'(g) - w(x) - w(p) \\ &= 2w'(x) - w(x) - w(p) \\ &\le 2(w'(x) - w(x)). \end{aligned} \]

Single Splay Operation:

Let \(w^{(n)}(x)=(w^{(n-1)})'(x)\) and \(w^{(0)}(x)=w(x)\). Suppose a splay operation accesses nodes \(x_{1}, x_{2}, \cdots, x_{n}\) in sequence, and finally \(x_{1}\) becomes the root node. This must involve several zig-zig and zig-zag operations and at most one zig operation. The amortized cost of the first two types of operations does not exceed \(3(w'(x)-w(x))\), and the amortized cost of the last operation does not exceed \(3(w'(x) - w(x))+1\). Therefore, the total amortized cost does not exceed

\[ 3(w^{(n)}(x_1) - w^{(0)}(x_1)) + 1 \le 3\log n + 1. \]

Hence, the amortized complexity of a single splay operation is \(O(\log n)\). Consequently, the time complexity of insertion, query, deletion, and other operations based on splaying is also amortized \(O(\log n)\).

Conclusion:

After performing \(m\) splay operations, the actual cost is

\[ \begin{aligned} \sum_{i=1}^m t_i &= \sum_{i=1}^m \left(c_i + \varphi_{i-1} - \varphi_i \right) \\ &= \sum_{i=1}^m c_i + \varphi_0 - \varphi_m \\ &\le m(3\log n+1) + n\log n. \end{aligned} \]

Therefore, the actual time complexity of \(m\) splay operations is \(O((m+n)\log n)\).

Why can the rebalancing operation of a Splay tree achieve an amortized complexity of \(O(\log n)\)?

The naive rebalancing idea is to repeatedly rotate a node upward until it becomes the root. The problem with this naive approach is that for a chain-like tree where all children are left (or right) children, it is equivalent to repeatedly performing zig operations. Thus, the constant term \(1\) in the amortized cost of the zig operation accumulates continuously, resulting in a final amortized complexity of \(O(\log n+n)\). The design of the Splay tree's rebalancing operation avoids the constant accumulation in consecutive zig scenarios, ensuring that during a complete splay operation, at most one standalone zig operation is performed, thereby optimizing the time complexity.

Balanced Tree Operations

This section discusses methods for implementing common balanced tree operations based on the Splay tree. Among them, the more important ones are finding elements by value or rank, which can locate a specific element and move it up to the root for subsequent processing.

As an example, this section will discuss the implementation of the template problem Normal Balanced Tree.

Search by Value

As a binary search tree, we can search for the corresponding node by value \(v\) by comparing the value \(v\) to be found with the value of the current node. After finding it, move the element up to the root.

Note that there are often situations where the corresponding node does not exist in the tree. For such cases, record the last accessed node (i.e., \(y\) in the implementation) and move \(y\) up to the root. At this point, the value stored in node \(y\) must be either the largest among all elements less than \(v\) (i.e., the predecessor of \(v\)) or the smallest among all elements greater than \(v\) (i.e., the successor of \(v\)). This is because the search process ensures that the left subtree always stores values less than \(v\), and the right subtree always stores values greater than \(v\).

Implementation 
1
2
3
4
5
void find(int& z, int v) {
  int x = z, y = fa[x];
  for (; x && val[x] != v; x = ch[y = x][v > val[x]]);
  splay(z, x ? x : y);
}

This implementation allows specifying any node \(z\) as the root node and searching by value within its subtree.

Access by Rank

Because subtree size information is recorded, the Splay tree can also access elements by rank, i.e., find the \(k\)-th smallest element in the tree.

Let \(k\) be the remaining rank. The specific steps are as follows:

  • If the left subtree is non-empty and the remaining rank \(k\) is not greater than the size of the left subtree, then search in the left subtree.
  • Otherwise, if \(k\) is not greater than the size of the left subtree plus the root, then the root node is the one we are looking for.
  • Otherwise, subtract the size of the left subtree and the root from \(k\), and continue searching in the right subtree.
  • Move the finally found element up to the root.
Implementation 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
void loc(int& z, int k) {
  int x = z;
  for (;;) {
    if (sz[ch[x][0]] >= k) {
      x = ch[x][0];
    } else if (sz[ch[x][0]] + cnt[x] >= k) {
      break;
    } else {
      k -= sz[ch[x][0]] + cnt[x];
      x = ch[x][1];
    }
  }
  splay(z, x);
}

This implementation needs to ensure that the rank \(k\) does not exceed the tree size at root \(z\).

Operation \(4\) in the template problem requires returning a value by rank. Simply call this method and return the value.

Implementation 
1
2
3
4
5
int find_kth(int k) {
  if (k > sz[rt]) return -1;
  loc(rt, k);
  return val[rt];
}

Merge Operation

Sometimes we need to merge two Splay trees.

Let the root nodes of the two trees be \(x\) and \(y\). To ensure the result is still a binary search tree, we require that the maximum value in tree \(x\) is less than the minimum value in tree \(y\). This condition can usually be satisfied because the two trees are often split from a larger subtree.

The merge operation is as follows:

  • If one or both of \(x\) and \(y\) are empty trees, directly return the root node of the non-empty tree or an empty tree.
  • Otherwise, use loc(y, 1) to move the minimum value in tree \(y\) up to the root \(y\), then set its left child (which must be empty at this point) to \(x\), update node information, and return node \(y\).
Implementation 
1
2
3
4
5
6
7
8
int merge(int x, int y) {
  if (!x || !y) return x | y;
  loc(y, 1);
  ch[y][0] = x;
  fa[x] = y;
  push_up(y);
  return y;
}

The split operation is similar. Therefore, the Splay tree can simulate the approach of non-rotating treap for various operations, including interval operations. Later sections will introduce interval operation handling methods more characteristic of Splay trees.

Insert Operation

The insert operation is a relatively complex process. The specific steps are as follows: (Assume the value to be inserted is \(v\))

  • Similar to the search-by-value process, search downward for the node storing \(v\) or an empty node based on \(v\), recording the parent node \(y\) during the process.
  • If a node \(x\) storing \(v\) exists, directly update its information; otherwise, create a new node \(x\).
  • Perform a splay operation to move the last node \(x\) up to the root.
Implementation 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
void insert(int v) {
  int x = rt, y = 0;
  for (; x && val[x] != v; x = ch[y = x][v > val[x]]);
  if (x) {
    ++cnt[x];
    ++sz[x];
  } else {
    x = ++id;
    val[x] = v;
    cnt[x] = sz[x] = 1;
    fa[x] = y;
    if (y) ch[y][v > val[y]] = x;
  }
  splay(rt, x);
}

This implementation allows directly inserting a value into an empty tree. If you don't want to handle empty trees, you can insert a dummy node into the tree in advance.

Delete Operation

The delete operation is also a relatively complex operation. The specific steps are as follows: (Assume the value to be deleted is \(v\))

  • First, search for the node storing it by value \(v\) and move it up to the root.
  • If the node storing it does not exist, return directly. (The splay operation has already been performed in the previous step.)
  • Otherwise, update the node information.
  • If the resulting root node is an empty node, merge the left and right subtrees as the new root node. Note that before merging, the parent nodes of the roots of the two subtrees need to be updated to empty.
Implementation 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
bool remove(int v) {
  find(rt, v);
  if (!rt || val[rt] != v) return false;
  --cnt[rt];
  --sz[rt];
  if (!cnt[rt]) {
    int x = ch[rt][0];
    int y = ch[rt][1];
    fa[x] = fa[y] = 0;
    rt = merge(x, y);
  }
  return true;
}

Query Rank

Directly access the node by value \(v\) (and move it up to the root), then return the corresponding value.

Note that when \(v\) does not exist, the relationship between the root returned by the method find(rt, v) and \(v\) cannot be determined and needs to be discussed separately.

Implementation 
1
2
3
4
int find_rank(int v) {
  find(rt, v);
  return sz[ch[rt][0]] + (val[rt] < v ? cnt[rt] : 0) + 1;
}

Query Predecessor

The predecessor is defined as the largest number less than \(v\). The specific steps are as follows:

  • Access the node by value \(v\) (and move it up to the root).
  • If the value at the root is less than \(v\), then it must be the largest one, so return it directly.
  • Otherwise, find the maximum value in the left subtree and move it up to the root.

The last step is equivalent to directly calling loc(ch[rt][0], sz[ch[rt][0]]), but it omits unnecessary checks.

Implementation 
1
2
3
4
5
6
7
8
9
int find_prev(int v) {
  find(rt, v);
  if (rt && val[rt] < v) return val[rt];
  int x = ch[rt][0];
  if (!x) return -1;
  for (; ch[x][1]; x = ch[x][1]);
  splay(rt, x);
  return val[rt];
}

This implementation allows the predecessor not to exist, in which case it returns \(-1\).

Query Successor

The successor is defined as the smallest number greater than \(x\). The query method is similar to the predecessor, except that the maximum value in the left subtree is replaced by the minimum value in the right subtree, i.e., calling loc(ch[rt][1], 1).

Implementation 
1
2
3
4
5
6
7
8
9
int find_next(int v) {
  find(rt, v);
  if (rt && val[rt] > v) return val[rt];
  int x = ch[rt][1];
  if (!x) return -1;
  for (; ch[x][0]; x = ch[x][0]);
  splay(rt, x);
  return val[rt];
}

Reference Implementation

At the end of this section, a reference implementation for the template problem Normal Balanced Tree is provided.

Reference Implementation 
  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
#include <iostream>

constexpr int N = 2e6;
int id, rt;
int fa[N], val[N], cnt[N], sz[N], ch[N][2];

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

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

void rotate(int x) {
  int y = fa[x], z = fa[y];
  bool r = dir(x);
  ch[y][r] = ch[x][!r];
  ch[x][!r] = y;
  if (z) ch[z][dir(y)] = x;
  if (ch[y][r]) fa[ch[y][r]] = y;
  fa[y] = x;
  fa[x] = z;
  push_up(y);
  push_up(x);
}

void splay(int& z, int x) {
  int w = fa[z];
  for (int y; (y = fa[x]) != w; rotate(x)) {
    if (fa[y] != w) rotate(dir(x) == dir(y) ? y : x);
  }
  z = x;
}

void find(int& z, int v) {
  int x = z, y = fa[x];
  for (; x && val[x] != v; x = ch[y = x][v > val[x]]);
  splay(z, x ? x : y);
}

void loc(int& z, int k) {
  int x = z;
  for (;;) {
    if (sz[ch[x][0]] >= k) {
      x = ch[x][0];
    } else if (sz[ch[x][0]] + cnt[x] >= k) {
      break;
    } else {
      k -= sz[ch[x][0]] + cnt[x];
      x = ch[x][1];
    }
  }
  splay(z, x);
}

int merge(int x, int y) {
  if (!x || !y) return x | y;
  loc(y, 1);
  ch[y][0] = x;
  fa[x] = y;
  push_up(y);
  return y;
}

void insert(int v) {
  int x = rt, y = 0;
  for (; x && val[x] != v; x = ch[y = x][v > val[x]]);
  if (x) {
    ++cnt[x];
    ++sz[x];
  } else {
    x = ++id;
    val[x] = v;
    cnt[x] = sz[x] = 1;
    fa[x] = y;
    if (y) ch[y][v > val[y]] = x;
  }
  splay(rt, x);
}

bool remove(int v) {
  find(rt, v);
  if (!rt || val[rt] != v) return false;
  --cnt[rt];
  --sz[rt];
  if (!cnt[rt]) {
    int x = ch[rt][0];
    int y = ch[rt][1];
    fa[x] = fa[y] = 0;
    rt = merge(x, y);
  }
  return true;
}

int find_rank(int v) {
  find(rt, v);
  return sz[ch[rt][0]] + (val[rt] < v ? cnt[rt] : 0) + 1;
}

int find_kth(int k) {
  if (k > sz[rt]) return -1;
  loc(rt, k);
  return val[rt];
}

int find_prev(int v) {
  find(rt, v);
  if (rt && val[rt] < v) return val[rt];
  int x = ch[rt][0];
  if (!x) return -1;
  for (; ch[x][1]; x = ch[x][1]);
  splay(rt, x);
  return val[rt];
}

int find_next(int v) {
  find(rt, v);
  if (rt && val[rt] > v) return val[rt];
  int x = ch[rt][1];
  if (!x) return -1;
  for (; ch[x][0]; x = ch[x][0]);
  splay(rt, x);
  return val[rt];
}

int main() {
  int n;
  std::cin >> n;
  for (; n; --n) {
    int op, x;
    std::cin >> op >> x;
    switch (op) {
      case 1:
        insert(x);
        break;
      case 2:
        remove(x);
        break;
      case 3:
        std::cout << find_rank(x) << '\n';
        break;
      case 4:
        std::cout << find_kth(x) << '\n';
        break;
      case 5:
        std::cout << find_prev(x) << '\n';
        break;
      case 6:
        std::cout << find_next(x) << '\n';
        break;
    }
  }
  return 0;
}

Sequence Operations

Splay trees can also be applied to sequences to maintain interval information. Compared to segment trees, Splay trees have a larger constant factor but support more complex sequence operations, such as interval reversal. As mentioned earlier, Splay trees also support split and merge operations, so they can simulate non-rotating treap for interval operations, which will not be discussed further here. This section mainly discusses the implementation method of interval operations based on splay operations.

The Splay tree built from a sequence has the following properties:

  • The in-order traversal of the Splay tree corresponds to the left-to-right traversal of the original sequence.
  • A node in the Splay tree represents an element in the original sequence.
  • A subtree in the Splay tree represents an interval in the original sequence.

Because of the splay operation, we can quickly extract the Splay subtree representing a certain interval.

As an example, this section will discuss the implementation of the template problem Literary Balanced Tree.

Building the Tree from a Sequence

Before operations, we need to build the Splay tree from the given sequence. Based on the properties of the Splay tree, we can directly build a chain with only left children. The time complexity is \(O(n)\).

Reference Implementation 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
void build(int n) {
  for (int i = 1; i <= n + 2; ++i) {
    ++id;
    ch[id][0] = rt;
    if (rt) fa[rt] = id;
    rt = id;
    val[id] = i - 1;
  }
  splay(rt, 1);
}

The final splay operation updates node information from bottom to top. For the convenience of later interval operations, two sentinel nodes are added to the left and right sides of the sequence.

Interval Reversal

Taking interval reversal as an example, we can understand the method of interval operations: (Let the interval be \([L,R]\))

  • First, move node \(L-1\) up to the root node, then in its right subtree, move node \(R+1\) up to the root of the right subtree.
  • At this point, let \(x\) be the left child of the root's right child. Then the subtree rooted at \(x\) corresponds to the interval \([L,R]\).
  • Perform the operation on interval \([L,R]\) at \(x\) and mark it with a lazy tag.
  • Propagate the tag once at \(x\), then use the splay operation to move \(x\) up to the root.

The operation needed in the first step is the "access by rank" from the balanced tree operations discussed earlier, because the label of an element is its rank. Due to the management of lazy tags, its implementation is slightly different from the above.

Reference Implementation 
1
2
3
4
5
6
7
8
void reverse(int l, int r) {
  loc(rt, l);
  loc(ch[rt][1], r - l + 2);
  int x = ch[ch[rt][1]][0];
  lazy_reverse(x);
  push_down(x);
  splay(rt, x);
}

The splay operation in the last step is not to ensure correct complexity but to update node information. Because the splay operation involves the left and right children of node \(x\), we need to propagate the tag at node \(x\) once beforehand. Of course, for the interval reversal operation specifically, reversing the subinterval does not affect ancestor nodes, so omitting this step is also correct. This implementation retains these two lines to illustrate the general approach.

Lazy Tag Management

First, we need the auxiliary functions lazy_reverse(x) and push_down(x). The former swaps left and right children and updates the lazy tag; the latter propagates the tag downward.

Reference Implementation 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
void lazy_reverse(int x) {
  std::swap(ch[x][0], ch[x][1]);
  lz[x] ^= 1;
}

void push_down(int x) {
  if (lz[x]) {
    if (ch[x][0]) lazy_reverse(ch[x][0]);
    if (ch[x][1]) lazy_reverse(ch[x][1]);
    lz[x] = 0;
  }
}

Then, we only need to propagate tags when moving downward through nodes. The operations required by the template problem are relatively simple; only the operation of finding by rank (i.e., loc) involves accessing nodes downward. Note that we need to propagate tags before the function accesses a new node each time.

Reference Implementation 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
void loc(int& z, int k) {
  int x = z;
  for (push_down(x); sz[ch[x][0]] != k - 1; push_down(x)) {
    if (sz[ch[x][0]] >= k) {
      x = ch[x][0];
    } else {
      k -= sz[ch[x][0]] + 1;
      x = ch[x][1];
    }
  }
  splay(z, x);
}

Because all lazy tags on the traversed path have been removed when accessing nodes downward, we no longer need to handle lazy tags when moving nodes up using the splay operation. However, we must be careful with the node involved in the interval operation: it is also on the path of the splay operation, but it has just been operated on and may have tags that have not been propagated yet. We need to propagate them first before performing the splay operation, as done above.

Reference Implementation

At the end of this section, a reference implementation for the template problem Literary Balanced Tree is provided.

Reference Implementation 
  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
#include <iostream>

constexpr int N = 2e6;
int id, rt;
int fa[N], val[N], sz[N], lz[N], ch[N][2];

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

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

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

void push_down(int x) {
  if (lz[x]) {
    if (ch[x][0]) lazy_reverse(ch[x][0]);
    if (ch[x][1]) lazy_reverse(ch[x][1]);
    lz[x] = 0;
  }
}

void rotate(int x) {
  int y = fa[x], z = fa[y];
  bool r = dir(x);
  ch[y][r] = ch[x][!r];
  ch[x][!r] = y;
  if (z) ch[z][dir(y)] = x;
  if (ch[y][r]) fa[ch[y][r]] = y;
  fa[y] = x;
  fa[x] = z;
  push_up(y);
  push_up(x);
}

void splay(int& z, int x) {
  int w = fa[z];
  for (int y; (y = fa[x]) != w; rotate(x)) {
    if (fa[y] != w) rotate(dir(x) == dir(y) ? y : x);
  }
  z = x;
}

void loc(int& z, int k) {
  int x = z;
  for (push_down(x); sz[ch[x][0]] != k - 1; push_down(x)) {
    if (sz[ch[x][0]] >= k) {
      x = ch[x][0];
    } else {
      k -= sz[ch[x][0]] + 1;
      x = ch[x][1];
    }
  }
  splay(z, x);
}

void build(int n) {
  for (int i = 1; i <= n + 2; ++i) {
    ++id;
    ch[id][0] = rt;
    if (rt) fa[rt] = id;
    rt = id;
    val[id] = i - 1;
  }
  splay(rt, 1);
}

void reverse(int l, int r) {
  loc(rt, l);
  loc(ch[rt][1], r - l + 2);
  int x = ch[ch[rt][1]][0];
  lazy_reverse(x);
  push_down(x);
  splay(rt, x);
}

void print(int x) {
  if (!x) return;
  push_down(x);
  print(ch[x][0]);
  std::cout << val[x] << ' ';
  print(ch[x][1]);
}

void print() {
  loc(rt, 1);
  loc(ch[rt][1], sz[rt] - 1);
  print(ch[ch[rt][1]][0]);
}

int main() {
  int n, m;
  std::cin >> n >> m;
  build(n);
  for (; m; --m) {
    int l, r;
    std::cin >> l >> r;
    reverse(l, r);
  }
  print();
  return 0;
}

Exercises

These problems are straightforward applications of Splay trees maintaining binary search trees:

Splay trees also appear in more complex application scenarios:

References and Notes

Parts of this article are referenced from the algocode algorithm blog. Special thanks!

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