Oct 26, 2022
Are you scared when you hear about all these pesky data structures like Fenwick Tree, RMQ, Segment Tree in competitive programming?
Are you afraid of writing code to solve problems like finding the minimum, maximum, or sum of some range query, especially when there are updates to the data?
Well, fear no more! In this tutorial I will introduce the Swiss knife of all sequence manipulation data structure, one code that can (theoretically) solve every problem of this kind, one tree to rule them all - the Splay Tree!
Disclaimer: One drawback of the Splay Tree is having a somewhat large constant despite being asymptotically amortized \( O(\log n) \). While generally good problems should not punish solutions for having a large constant, using it on very strict problems has a risk of TLE (you can always substitute it with a less-demanding data structure if constant is the issue, though).
The easiest way to store a sequence of data: \( (1, 2, 4, 5, 6) \) is to put them in an array. An array is a simple and very good data structure that allows us to look up each element in \( O(1) \) time from the index.
However, the problem comes up when we want to insert some data into the sequence: let us say we want to put \( 3 \) between \( 2 \) and \( 4 \). Then there suddenly is no good way for an array to perform this operation except to move every element after \( 3 \), i.e. \( 4, 5, 6\), which results in \( O(n) \) complexity for \( n \) elements.
For those of you who have taken a data structure course in the college, you know that a linked list can do the reverse of an array: it can insert an element in \( O(1) \) but needs to look up an element in \( O(n) \) complexity. This is still not ideal, so let us try to solve the problem with a binary tree.
First, we need some way to establish the relation between a binary and a sequence. We will take the easy way: assume that everyone of the left subtree of a node comes before the node, and the right subtree of a node comes after the node. Note that this definition uniquely determines a sequence of nodes from a tree (also known as the in-order, for those who have taken a data structure course). The above example can thus be represented by this tree:
It is very easy to write code to find the \( i \)-th element of any tree and to insert an element:
Note: all codes in this tutorial are designed to minimize ICPC typing time, and thus disregard readability and common coding practice recklessly. I have added some comment to make them more readable, but I still encourage you to write a more 'readable' implementation on your own to make sure you understand the concept :)
Now let us take a moment to analyze the complexity of the algorithm. We can infer that the complexity of any operation above is the height of the tree \( O(h) \), and a binary tree can store \( n \) elements in \( \log n \) height, so we have good chances to make the complexity of both finding an element and inserting one \( O(\log n) \).
Unfortunately, using a tree to solve the problem is not so easy. A binary tree can degrade to a 'stick' tree if we do not pay attention. Consider this tree, which also represents the example above:
This type of 'stick' tree has a height of \( n \), which destroys our complexity assumption. Therefore, we need some method to maintain the height of our binary tree as low as \( O(\log n) \) in order for our complexity assumption to hold. This act is called to 'balance' a tree, and there are many ways to do so: AVL, Red-Black Tree, Scapegoat Tree, etc. However, we are going to introduce the only method capable of not only maintaining the balance of our tree, but also keeping track of auxiliary information that allows us to figure out those pesky 'sum of the segment of the sequence' problems - the Splay Tree!
To balance a binary tree, we need some tools. One common tool is known as a rotation:
Node \( n \) and \( p \) represents two nodes that we care about, and \( A, B, C \) are three subtrees of these nodes. Notice that both the left and the right tree has an in-order of \( (A, n, B, p, C) \), but they have slightly different height. Also notice that we can change the root of the tree to \( n \) via a rotation (i.e. rotate \( n \) up).
We can try to program this behavior in 10 lines:
The primitive idea of Splay is very simple: bad cases in binary trees occur because the node we access is very far down of the tree (i.e. has a very large height). Therefore, to reduce the cost of accessing this node in the future, we should rotate this node up. In fact, every time we access the node, let us rotate the node to the root!
Unfortunately, This does not quite work. Rotating the bottom node on a 'stick' tree to the root gives us another 'stick'-ish tree, which is not helpful in reducing the complexity:
Therefore, we need to use a new strategy to rotate a node to the top. Enter Splay:
In a splay operation, we usually rotate node \( n \) up twice back-to-back to reduce its height by 2 (known as Zig-Zag):
However, there is a catch: if node \( n \) and its parent \( m \) are on the same side (i.e. both are the left children or both are the right children), instead of rotating \( n \) up twice, we rotate \( m \) up once first, then \( n \) up once, which also reduces its height by 2, like this (known as Zig-Zig, because two rotations are in the same direction):
Note: In the scenario where the parent of \( n \) is the root, it suffices to rotate \( n \) to the root directly in one rotation (known as Zig).
It is not immediately obvious why Zig-Zig works: the tree looks like a stick before and after the operation! But if we do it on the previous example it becomes more apparent.
Note: This part is skippable if you do not want to know why Splay works. I think it is really interesting, though!
Let us consider how we should argue the complexity of a dynamic rotating tree \( T \) over a sequence of find-and-then-splay-to-top operations \( Q \).
We first observe that finding a node has the same time complexity as splaying a node to the root, because they both access the node's path to the root and nothing else. We will restrict our discussion to the complexity of splaying a node to the root in the following analysis.
One common idea here is the Potential Method, which gives us a battery in addtion to executing the algorithm:
At the end of the execution, we can see that our total execution time is
\[ \text{the number of operations we used} + \text{the difference in battery before and after the execution.} \]Usually we want our battery to be something indicative of the data structure we are using. In this case we define our battery \( \Phi \) of a tree \( T \) to be:
\[ \begin{align} k&=\text{the number of operations it takes to perform a splay operation}\text{,}\\ \text{size}(n)&=\text{the size of the subtree with root at }n\text{,}\\ \text{rank}(n)&=\log_2\text{size}(n)\text{,}\\ \Phi&=k\sum_{n\in T}\text{rank}(n)\text{.} \end{align} \]Observe that \( \text{rank}(n) \leq \log|T| \), so \( 0 \leq \Phi \leq k|T|\log|T| \), which means that we have already bound the difference in battery before and after the execution \( \Delta\Phi \) to \( O(|T|\log|T|) \). Now we only need to ensure that each operation takes \( O(\log|T|) \) time, and we will have a very nice complexity of \( O((|Q|+|T|)\log|T|) \).
Let us consider the case of a Zig-Zag:
Since \( \text{rank}(l)=\text{rank}'(n) \) (both are the whole subtree),
\[ \begin{align} \text{TIME}(\text{Zig-Zag})&=k(1+\text{rank}'(m)+\text{rank}'(l)-\text{rank}(n)-\text{rank}(m))\\ &< k(1+\text{rank}'(m)+\text{rank}'(l)-2\text{rank}(n))\\ \end{align} \]Since
\[ \begin{align} 1+\text{rank}'(m)+\text{rank}'(l)&=\log 2+\log \text{size}'(m)+\log \text{size}'(l)\\ &=\log 2\text{size}'(m)\text{size}'(l)\\ &<\log (\text{size}'(m)+\text{size}'(l))^2\\ &<\log \text{size}'^2(n)\\ &=\log \text{size}'(n)+\log \text{size}'(n)=2\text{rank}'(n)\text{,}\\ \end{align} \]We demonstrate
\[ \text{TIME}(\text{Zig-Zag})<k(2\text{rank}'(n)-2\text{rank}(n))=2k(\text{rank}'(n)-\text{rank}(n))\text{.} \]Applying the same reasoning to the Zig-Zig case:
And now we are going to use the unique property of the Zig-Zig operation - that
\[ \text{size}(n)+\text{size}'(l)+1=(\text{size}(A)+\text{size}(B)+1)+(\text{size}(C)+\text{size}(D)+1)+1=\text{size}'(n)\text{.} \]Therefore,
\[ \begin{align} \text{TIME}(\text{Zig-Zig})&<k(\log 2\text{size}'(m)\text{size}'(l)-2\text{rank}(n))\\ &=k(\log 2\text{size}'(m)(\text{size}'(n)-\text{size}(n)-1)-2\text{rank}(n))\\ &<k(\log 2\text{size}'(n)(\text{size}'(n)-\text{size}(n))-2\text{rank}(n))\\ &=k(\log 2\text{size}'(n)(\text{size}'(n)-\text{size}(n))+\text{rank}(n)-3\text{rank}(n))\\ &=k(\log 2\text{size}'(n)(\text{size}'(n)-\text{size}(n))+\log\text{size}(n)-3\text{rank}(n))\\ &=k(\log 2\text{size}'(n)\text{size}(n)(\text{size}'(n)-\text{size}(n))-3\text{rank}(n))\text{.} \end{align} \]Since
\[ \text{size}(n)(\text{size}'(n)-\text{size}(n)) < \frac{1}{4}\text{size}'^2(n) < \frac{1}{2}\text{size}'^2(n)\text{,} \] \[ \begin{align} \text{TIME}(\text{Zig-Zig})&<k(\log 2\text{size}'(n)\text{size}(n)(\text{size}'(n)-\text{size}(n))-3\text{rank}(n))\\ &<k(\log \text{size}'^3(n)-3\text{rank}(n))=3k(\text{rank}'(n)-\text{rank}(n))\text{.} \end{align} \]We conclude that
\[ \text{TIME}(\text{Zig-Zag}),\text{TIME}(\text{Zig-Zig})<3k(\text{rank}'(n)-\text{rank}(n))\text{.} \]Since splaying to the root is a series of Zig-Zag and Zig-Zig operations that starts with a node of rank \( \text{rank}(n) \) and ends with a node of rank \( \text{rank}(\text{root}) = \log|T| \),
\[ \begin{align} \text{TIME}(\text{Splay-to-root})=3k(\text{rank}(\text{root})-\text{rank}(n))=O(\log |T|)\text{.} \end{align} \]And we have bound the splay-to-root operation to \( O(\log |T|) \) time complexity.
With all the maths out of the way we can start actually writing the code to do Splay operations in 10 lines:
To recap what we have done, we have implemented a Splay Tree that allows
in amortized \( O(\log n) \) time, which is cool because \( O(\log n) \) is very small. We are going to look at some more use cases, and I will provide a concrete example with code.
The most common thing to do in a sequence \( (x_1,x_2,\ldots,x_n) \) is probably to find the sum of a segment \( \sum_{i=l}^{r}x_i \).
It may surprise you that we have already (sort of) implemented in our previoud code. Recall that we have kept track of each node's subtree size with node.size and node.update(). It turns out that we can keep track of each node's subtree sum in the same way. The problem is then to find a subtree that corresponds to \( [x_l,x_r] \).
The solution is quite strightforward: we can splay node \( x_{r+1} \) to root, and node \( x_{l-1} \) to just below \( x_{r+1} \). Then a subtree that corresponds to \( [x_l,x_r] \) will appear:
Note: This assumes that \( x_{l-1} \) and \( x_{r+1} \) exist. In pratice this is trivially ensured by adding a dummy head and a dummy tail to the tree.
Deletion in Splay is easy: say we want to delete a segment \( [x_l,x_r] \). We only need to find a subtree that corresponds to \( [x_l,x_r] \), and drop it.
Often times we need to manipulate a segment \( [x_l,x_r] \) in some way: add some value, set the value to something, etc. We will look at a example where we want to set every element in \( [x_l,x_r] \) to some value \( v \).
The way to implement the operation is to maintain a lazy label on every node. A lazy label can either be null or some value. If the label \( c \) is not null, then we treat the corresponding node's subtree as if every node in that subtree has a value of \( c \). Therefore, to apply the operation, we only need to find the subtree of \( [x_l,x_r] \) and give the root a value and a label of \( c \).
Obviously, when we actually try to use a node, we need to make sure that its ancestors do not have any lazy labels, because these labels can interfere with the node's value. Fortunately, we can use push_down to clear the label for every ancestor node, starting from the root:
push_down repeatedly:
Finally we are going to look at an interesting example: reversing a segment \( [x_l,x_r] \) in the sequence to \( (x_r, x_{r-1}, \ldots, x_l) \).
We implement this operation in the same way above: Maintain a label to record if the subtree should be reversed. Then, when doing push_down:
We are going to look at this problem from POJ 3580.
I prefer a more template-based approach in these large data structure problems: copy-paste everything verbatim from the template and add code only after the template. I have added some comment in the code, so see if you can follow it: