🗂️Data StructureAdvanced

Splay Tree

Key Points

  • •
    A splay tree is a self-adjusting binary search tree that moves the most recently accessed node to the root with rotations.
  • •
    The core splay operation uses three cases called zig, zig-zig, and zig-zag to restructure the tree around the accessed node.
  • •
    Although a single operation can be linear in the worst case, the amortized time per search/insert/delete is O(log n).
  • •
    Splay trees exploit locality of reference: recently or frequently accessed keys become faster to reach.
  • •
    They naturally support split and join (merge) operations in O(log n) amortized time without extra random bits or colors.
  • •
    Implicit-key splay trees can represent sequences and support range operations like reverse using lazy propagation.
  • •
    They form the backbone of advanced structures like Link-Cut Trees for dynamic trees.
  • •
    Splay trees are pointer-heavy; careful implementation of rotations, parent updates, and lazy flags is essential.

Prerequisites

  • →Binary Search Trees — Understanding the BST property and how search/insert/delete work is essential before adding splay rotations.
  • →Tree Rotations — Splay operations are sequences of rotations; you must be comfortable with left/right rotations and pointer updates.
  • →Amortized Analysis and Potential Method — The O(log n) guarantee is amortized; the potential function explains why sequences of operations are efficient.
  • →Pointer Manipulation in C++ — Implementing splay trees requires careful parent/child pointer maintenance and memory management.
  • →Lazy Propagation in Trees — Implicit-key splay trees often use lazy flags (e.g., reverse) that must be pushed before rotations or traversals.

Detailed Explanation

Tap terms for definitions

01Overview

Hook: Imagine a library where the most borrowed books always end up on the front shelf. Each time a book is borrowed, the librarian moves it closer to the front so that the next borrow will be faster. Concept: That is the spirit of a splay tree—a binary search tree (BST) that self-adjusts after every access so that recently touched nodes move near the root. It does this with a simple, unified restructuring step called splaying, composed of rotations (zig, zig-zig, zig-zag). Over time, this leads to excellent average performance. Example: If your program queries the same few keys repeatedly (like the current maximum, or a small group of hot items), a splay tree quickly arranges itself so those keys live near the root, making subsequent operations faster. Splay trees maintain the BST property (left subtree keys are smaller, right subtree keys are larger) but do not maintain strict balance like AVL or Red-Black Trees. Instead, they rely on amortized analysis: while a single operation may be slow, any sequence of m operations costs at most O(m log n) overall. This simplicity (no colors, no priorities) and strong theoretical guarantees make splay trees a powerful tool in competitive programming and as a core primitive in advanced data structures.

02Intuition & Analogies

Think of a long hallway of lockers (keys) ordered by number. If a student keeps opening locker 37, the school custodian eventually moves locker 37 closer to the entrance so the student spends less time walking. Each time the student opens a locker, it gets pulled toward the entrance. Over days, the pattern of frequent access shapes the hallway so the most used lockers are near the front. In a splay tree, the hallway is a search path from the root to a node, and the custodian’s move is a sequence of rotations called splaying that brings the accessed node to the root. There are three cases during the climb: zig (one rotation when the node’s parent is the root), zig-zig (two rotations in the same direction when the node and parent are both left or both right children), and zig-zag (two rotations in opposite directions when the node is a left child and its parent is a right child, or vice versa). These moves are local but have a global effect: deeply nested frequently used nodes bubble up and stay closer to the top. This behavior is great for workloads with locality: if you touch nearby keys repeatedly, the tree molds itself to your pattern, making those accesses cheaper. Just like a bookshelf that reorders itself based on what you grab most, a splay tree is always learning from your last move and setting you up for a faster next one.

03Formal Definition

A splay tree is a binary search tree supporting standard dictionary operations (search, insert, delete) augmented with a splay(x) operation that, given a node x (or the last accessed node if x is absent), rotates x along the access path until x becomes the root. The splay step consists of repeated applications of the following cases: - Zig: x’s parent p is the root; rotate x over p once. - Zig-Zig: x and its parent p are both left children or both right children; rotate p over its parent g, then rotate x over the new parent. - Zig-Zag: x and its parent p are on opposite sides; rotate x over p, then rotate x over its new parent g. The BST invariant holds at all times. The Sleator–Tarjan potential method uses the potential function Φ(T) = Σ_v log s(v) where s(v) is the size of v’s subtree to show that any access operation has amortized time O(log n). In particular, the Access Lemma bounds the amortized cost of splaying node x by O(log(n)), more precisely by a constant times log(W/w(x)) in the weighted version. As a consequence, sequences of m operations on a tree with at most n nodes take O(m log n) time in total, even though a single operation may take Θ(n) rotations in the worst case.

04When to Use

Use a splay tree when:

  • You need a general-purpose ordered set/map with excellent amortized O(log n) performance and very simple code (no color or height maintenance).
  • Your workload exhibits temporal/spatial locality (e.g., repeatedly accessing a small set of keys or adjacent ranges). The tree adapts and keeps hot items near the root.
  • You want split and join (merge) in O(log n) amortized time with minimal extra machinery. This is useful in problems that need to partition or concatenate ordered sets.
  • You need an implicit-key tree (sequence) to support operations like kth, range reverse, cut-paste, and rotate with lazy propagation; splay trees are a classic option alongside treaps.
  • You plan to implement Link-Cut Trees for dynamic tree queries; splay trees are the fundamental component for preferred path maintenance. Avoid splay trees when you need strict worst-case O(log n) per operation (e.g., real-time or latency-critical single operations) or when constant factors of rotations are an issue and your access pattern has no locality; in such cases, AVL/Red-Black/treaps or order-statistic trees might be preferable.

⚠️Common Mistakes

  • Incorrect rotations and parent/child updates: Failing to fix all parent pointers, or forgetting to reattach the rotated subtree to the grandparent, causes subtle corruption. Always handle the three pointers (node, parent, grandparent) and update sizes after each rotation.
  • Not pushing lazy flags before rotations (implicit splay): When using reverse/lazy tags for sequences, you must push pending flags down along the access path before rotating; otherwise, subtree structures and sizes become inconsistent.
  • Forgetting to update subtree sizes/counts: If you track size or duplicate counts, ensure every structural change (link, cut, rotate, increment/decrement counts) is followed by a pull/update.
  • Mishandling duplicates: Decide on a policy (store counts in nodes vs. allow equal keys to go left/right consistently). Mixing strategies leads to broken rank/kth queries.
  • Splaying the wrong node after operations: After search, splay the found node or the last accessed node; after insert/erase, make sure the intended node becomes root to reap amortization and to make subsequent joins/splits trivial.
  • Ignoring edge cases in split/join: join(left, right) requires all keys in left < all keys in right. Splay the maximum of left before attaching right, and be mindful of empty trees.
  • Deep recursion: Prefer iterative splay/rotate to avoid stack overflows in adversarial cases. Also watch memory management in C++ to avoid leaks (consider pools or smart pointers in production).

Key Formulas

Splay Tree Potential

Explanation: The potential is the sum of logs of subtree sizes. It captures how 'unbalanced' the tree is and is used to prove amortized bounds.

Access Lemma (Unweighted Form)

Explanation: The amortized cost A(x) to splay node x is bounded by a constant times the change in potential. Since s(root) n and s(x) 1, this implies O( n) amortized time.

Weighted Access Lemma

Explanation: With node weights summing to W, the amortized access cost depends on the weight of x. Heavier nodes are cheaper to access on average.

Total Cost Over m Operations

Explanation: Any sequence of m operations on a splay tree with at most n nodes takes O(m log n) time. Occasional expensive operations are 'paid for' by cheap ones.

Rank Definition

Explanation: The rank of x is the count of elements strictly smaller than x. It can be computed by traversing and summing left subtree sizes and duplicate counts.

kth Smallest via Sizes

Explanation: To find the kth element, repeatedly compare k with the size of the left subtree plus the node’s count to decide to go left, return current, or go right.

Split Specification

Explanation: Splitting by a key x produces two BSTs with all keys in L strictly less than x and all keys in R at least x. Implemented by splaying the lowe(x).

Join Procedure

Explanation: To join, bring the maximum of L to the root so it has no right child, then attach R as its right subtree. This runs in amortized O(log n).

Complexity Analysis

Splay trees guarantee O(log n) amortized time per operation (search, insert, delete, split, join). The analysis uses a potential function Φ(T) = Σ_v log s(v), where s(v) is the subtree size at v. Each splay step (zig, zig-zig, zig-zag) either significantly reduces the depth of the accessed node or redistributes potential so that expensive operations are infrequent. The Access Lemma shows that splaying node x costs at most a constant times the change in potential plus a small overhead, yielding O(log n) amortized complexity because s(root) ≤ n and s(x) ≥ 1. In worst-case individual operations, time can be Θ(n) (e.g., accessing the deepest leaf of a degenerate tree). However, over any sequence of m operations on a tree with at most n elements, the total time is O(m log n). Practically, this means that if you perform many operations, the average time per operation remains logarithmic even when some are slow. Space complexity is O(n) for n nodes, storing parent pointers, two child pointers, and optional metadata (size, count, lazy flags). Operations are typically implemented iteratively, giving O(1) auxiliary space. For implicit-key variants with lazy propagation, we often maintain a boolean reverse flag and subtree size; pushing flags is O(1) per visited node. Split and join are composed of a constant number of splay operations and pointer rewires, thus also O(log n) amortized time and O(1) extra space. Overall, splay trees trade strict worst-case bounds for simplicity and strong amortized guarantees while capitalizing on locality of reference.

Code Examples

Core Splay Tree (Ordered Multiset) with rank/kth, predecessor/successor
1#include <bits/stdc++.h>
2using namespace std;
3
4struct Node {
5    int key;
6    int cnt;          // number of duplicates stored at this node
7    int sz;           // size of subtree = left.sz + right.sz + cnt
8    Node *p, *l, *r;
9    Node(int k): key(k), cnt(1), sz(1), p(nullptr), l(nullptr), r(nullptr) {}
10};
11
12struct Splay {
13    Node* root = nullptr;
14
15    int size(Node* x) const { return x ? x->sz : 0; }
16    void pull(Node* x) {
17        if (!x) return;
18        x->sz = x->cnt + size(x->l) + size(x->r);
19    }
20    bool isLeft(Node* x) { return x->p && x->p->l == x; }
21
22    void connect(Node* x, Node* p, bool leftChild) {
23        if (x) x->p = p;
24        if (!p) return;
25        if (leftChild) p->l = x; else p->r = x;
26    }
27
28    void rotate(Node* x) {
29        Node* p = x->p;
30        Node* g = p ? p->p : nullptr;
31        if (!p) return;
32        bool xLeft = (x == p->l);
33        // Perform rotation
34        if (xLeft) {
35            connect(x->r, p, true);    // p->l = x->r
36            connect(p, x, false);      // x->r = p
37        } else {
38            connect(x->l, p, false);   // p->r = x->l
39            connect(p, x, true);       // x->l = p
40        }
41        // Attach x to grandparent
42        if (g) connect(x, g, p == g->l); else x->p = nullptr;
43        // Update sizes bottom-up
44        pull(p);
45        pull(x);
46    }
47
48    void splay(Node* x, Node* to = nullptr) {
49        if (!x) return;
50        while (x->p != to) {
51            Node* p = x->p;
52            Node* g = p->p;
53            if (g != to) {
54                bool zigzig = ( (x == p->l) == (p == g->l) );
55                if (zigzig) rotate(p); else rotate(x);
56            }
57            rotate(x);
58        }
59        if (!to) root = x;
60    }
61
62    Node* lower_bound_node(int k) {
63        Node* cur = root; Node* ans = nullptr; Node* last = nullptr;
64        while (cur) {
65            last = cur;
66            if (k <= cur->key) { ans = cur; cur = cur->l; }
67            else cur = cur->r;
68        }
69        if (last) splay(last);
70        if (ans) splay(ans);
71        return ans; // may be null if all keys < k
72    }
73
74    bool contains(int k) {
75        Node* cur = root; Node* last = nullptr;
76        while (cur) {
77            last = cur;
78            if (k == cur->key) { splay(cur); return true; }
79            cur = (k < last->key) ? last->l : last->r;
80        }
81        if (last) splay(last); // splay last accessed to root
82        return false;
83    }
84
85    void insert(int k) {
86        if (!root) { root = new Node(k); return; }
87        Node* cur = root; Node* p = nullptr;
88        while (cur) {
89            p = cur;
90            if (k == cur->key) { cur->cnt++; pull(cur); splay(cur); return; }
91            cur = (k < cur->key) ? cur->l : cur->r;
92        }
93        Node* x = new Node(k);
94        if (k < p->key) p->l = x; else p->r = x; x->p = p;
95        splay(x);
96    }
97
98    // Join: assumes all keys in L < all keys in R
99    Node* join(Node* L, Node* R) {
100        if (!L) return R; if (!R) return L;
101        // Splay max(L) to root
102        Node* cur = L;
103        while (cur->r) cur = cur->r;
104        // Make cur parentless root of L
105        Splay tmp; tmp.root = L; tmp.splay(cur);
106        cur->r = R; if (R) R->p = cur; pull(cur);
107        return cur;
108    }
109
110    void erase(int k) {
111        if (!contains(k)) return; // splay brings k to root if exists
112        if (root->key == k && root->cnt > 1) { root->cnt--; pull(root); return; }
113        Node* L = root->l; Node* R = root->r;
114        if (L) L->p = nullptr; if (R) R->p = nullptr;
115        delete root;
116        root = join(L, R);
117    }
118
119    // rank: number of keys < k
120    int rank_of(int k) {
121        int res = 0; Node* cur = root; Node* last = nullptr;
122        while (cur) {
123            last = cur;
124            if (k <= cur->key) cur = cur->l;
125            else { res += size(cur->l) + cur->cnt; cur = cur->r; }
126        }
127        if (last) splay(last);
128        return res;
129    }
130
131    // kth: 1-indexed by multiplicity
132    int kth(int k) {
133        Node* cur = root;
134        if (!cur || k <= 0 || k > size(cur)) throw runtime_error("k out of bounds");
135        while (cur) {
136            int leftSize = size(cur->l);
137            if (k <= leftSize) cur = cur->l;
138            else if (k <= leftSize + cur->cnt) { splay(cur); return cur->key; }
139            else { k -= leftSize + cur->cnt; cur = cur->r; }
140        }
141        throw runtime_error("unreachable");
142    }
143
144    // predecessor of k (strictly less). Returns optional<int>
145    optional<int> predecessor(int k) {
146        lower_bound_node(k); // now root is lower_bound or last
147        Node* cur = root;
148        if (!cur) return nullopt;
149        if (cur->key < k) return cur->key; // lower_bound didn't exist; cur is max
150        // go to left subtree's max
151        Node* p = cur->l;
152        if (!p) return nullopt;
153        while (p->r) p = p->r;
154        splay(p);
155        return p->key;
156    }
157
158    // successor of k (strictly greater). Returns optional<int>
159    optional<int> successor(int k) {
160        Node* lb = lower_bound_node(k+1); // first >= k+1
161        if (!lb) return nullopt; // all < k+1
162        return lb->key;
163    }
164
165    void inorder(Node* x, vector<pair<int,int>>& out) const {
166        if (!x) return;
167        inorder(x->l, out);
168        out.push_back({x->key, x->cnt});
169        inorder(x->r, out);
170    }
171    vector<pair<int,int>> to_vector() const {
172        vector<pair<int,int>> v; inorder(root, v); return v;
173    }
174};
175
176int main() {
177    ios::sync_with_stdio(false);
178    cin.tie(nullptr);
179
180    Splay T;
181    // Demo operations
182    vector<int> a = {5, 3, 9, 3, 7, 1, 9, 9};
183    for (int x : a) T.insert(x);
184
185    cout << "rank(7) = " << T.rank_of(7) << "\n";           // count < 7
186    cout << "kth(3) = " << T.kth(3) << "\n";                 // 3rd smallest by multiplicity
187
188    auto pred = T.predecessor(6); if (pred) cout << "pred(6) = " << *pred << "\n"; else cout << "no pred\n";
189    auto succ = T.successor(6); if (succ) cout << "succ(6) = " << *succ << "\n"; else cout << "no succ\n";
190
191    T.erase(9); // remove one 9
192    T.erase(2); // no effect
193
194    auto v = T.to_vector();
195    cout << "Inorder (val:cnt):";
196    for (auto [k,c]: v) cout << ' ' << k << ':' << c;
197    cout << "\n";
198    return 0;
199}
200

This program implements a classic key-based splay tree with duplicate counts (multiset). It supports insert, erase, search (contains), rank (count of elements less than a key), kth (1-indexed by multiplicity), predecessor, successor, inorder traversal, and exposes split/join logic inside erase. Rotations, splaying, and subtree size maintenance provide O(log n) amortized operations.

Time: Amortized O(log n) per operation (search/insert/erase/rank/kth)Space: O(n) for n nodes; O(1) auxiliary per operation
Split and Join (Merge) by Key using Splay
1#include <bits/stdc++.h>
2using namespace std;
3
4struct Node {
5    int key, sz, cnt; Node *p, *l, *r;
6    Node(int k): key(k), sz(1), cnt(1), p(nullptr), l(nullptr), r(nullptr) {}
7};
8
9int size(Node* x){ return x ? x->sz : 0; }
10void pull(Node* x){ if(x) x->sz = x->cnt + size(x->l) + size(x->r); }
11
12bool isLeft(Node* x){ return x->p && x->p->l == x; }
13void connect(Node* x, Node* p, bool left){ if(x) x->p = p; if(!p) return; if(left) p->l = x; else p->r = x; }
14
15void rotate(Node*& root, Node* x){
16    Node* p = x->p; if(!p) return; Node* g = p->p;
17    if (x == p->l) { connect(x->r, p, true); connect(p, x, false); }
18    else { connect(x->l, p, false); connect(p, x, true); }
19    if (g) connect(x, g, p==g->l); else x->p = nullptr, root = x;
20    pull(p); pull(x);
21}
22
23void splay(Node*& root, Node* x, Node* to=nullptr){
24    if(!x) return; while (x->p != to){ Node* p = x->p; Node* g = p->p; if (g != to){ bool zigzig = ((x==p->l)==(p==g->l)); if(zigzig) rotate(root,p); else rotate(root,x);} rotate(root,x);} if(!to) root = x; }
25
26Node* build_from_sorted(vector<int>& a, int l, int r){
27    if(l>r) return nullptr; int m=(l+r)/2; Node* x=new Node(a[m]); x->cnt=1; x->l=build_from_sorted(a,l,m-1); if(x->l) x->l->p=x; x->r=build_from_sorted(a,m+1,r); if(x->r) x->r->p=x; pull(x); return x; }
28
29Node* lower_bound_node(Node*& root, int k){
30    Node* cur=root; Node* ans=nullptr; Node* last=nullptr;
31    while(cur){ last=cur; if(k<=cur->key){ ans=cur; cur=cur->l; } else cur=cur->r; }
32    if(last) splay(root,last); if(ans) splay(root,ans); return ans;
33}
34
35pair<Node*,Node*> split_by_key(Node* root, int key){
36    if(!root) return {nullptr,nullptr};
37    Node* lb = lower_bound_node(root, key);
38    if(!lb){ // all keys < key
39        return {root, nullptr};
40    }
41    // lb is first >= key and at root
42    Node* L = lb->l; if(L) L->p=nullptr; lb->l=nullptr; pull(lb);
43    return {L, lb};
44}
45
46Node* join(Node* L, Node* R){
47    if(!L) return R; if(!R) return L;
48    // splay max(L)
49    Node* cur = L; while(cur->r) cur=cur->r; splay(L, cur);
50    cur->r = R; if(R) R->p = cur; pull(cur); return cur;
51}
52
53void inorder(Node* x, vector<int>& out){ if(!x) return; inorder(x->l,out); for(int i=0;i<x->cnt;i++) out.push_back(x->key); inorder(x->r,out);} 
54
55int main(){
56    ios::sync_with_stdio(false); cin.tie(nullptr);
57
58    // Build a splay tree from sorted array for demo
59    vector<int> a = {1,2,3,5,7,9};
60    Node* root = build_from_sorted(a, 0, (int)a.size()-1);
61
62    // Split by key 6: left contains <6, right contains >=6
63    auto [L, R] = split_by_key(root, 6);
64
65    vector<int> vL, vR; inorder(L, vL); inorder(R, vR);
66    cout << "Left:"; for(int x: vL) cout << ' ' << x; cout << "\n";
67    cout << "Right:"; for(int x: vR) cout << ' ' << x; cout << "\n";
68
69    // Join back
70    Node* J = join(L, R);
71    vector<int> vJ; inorder(J, vJ); cout << "Joined:"; for(int x: vJ) cout << ' ' << x; cout << "\n";
72    return 0;
73}
74

This program demonstrates splitting a splay tree by a key into two trees (keys < key, and keys ≥ key), then joining them back. The split is implemented by splaying the lower_bound(key) to the root and detaching its left subtree. Join splays the maximum of the left tree so that it has no right child, and then attaches the right tree. Both operations are amortized O(log n).

Time: Amortized O(log n) for split and joinSpace: O(n) storage; O(1) auxiliary per operation
Implicit-Key Splay Tree for Sequences with Range Reverse (Lazy Propagation)
1#include <bits/stdc++.h>
2using namespace std;
3
4struct Node {
5    int val;              // stored sequence value
6    int sz;               // subtree size (number of nodes)
7    bool rev;             // lazy reverse flag
8    Node *p, *l, *r;
9    Node(int v): val(v), sz(1), rev(false), p(nullptr), l(nullptr), r(nullptr) {}
10};
11
12int size(Node* x){ return x ? x->sz : 0; }
13
14void push(Node* x){
15    if (!x || !x->rev) return;
16    x->rev = false;
17    swap(x->l, x->r);
18    if (x->l) x->l->rev ^= 1;
19    if (x->r) x->r->rev ^= 1;
20}
21
22void pull(Node* x){ if(x) x->sz = 1 + size(x->l) + size(x->r); }
23
24void connect(Node* x, Node* p, bool left){ if(x) x->p = p; if(!p) return; if(left) p->l = x; else p->r = x; }
25
26void rotate(Node*& root, Node* x){
27    Node* p = x->p; if(!p) return; Node* g = p->p;
28    push(p); push(x); // ensure correctness under lazy flags
29    if (x == p->l) { connect(x->r, p, true); connect(p, x, false); }
30    else { connect(x->l, p, false); connect(p, x, true); }
31    if (g) connect(x, g, p==g->l); else x->p = nullptr, root = x;
32    pull(p); pull(x);
33}
34
35void splay(Node*& root, Node* x, Node* to=nullptr){
36    if(!x) return;
37    // Push path from top to x before rotations
38    auto pushPath = [&](Node* a){ vector<Node*> st; Node* cur=a; while(cur){ st.push_back(cur); cur=cur->p; } reverse(st.begin(), st.end()); for(Node* t: st) push(t); };
39    pushPath(x);
40    while (x->p != to){
41        Node* p = x->p; Node* g = p->p;
42        if (g != to){
43            // prepare for double rotation
44            push(g); push(p); push(x);
45            bool zigzig = ((x==p->l) == (p==g->l));
46            if (zigzig) rotate(root, p); else rotate(root, x);
47        }
48        push(p); push(x);
49        rotate(root, x);
50    }
51    pull(x);
52    if(!to) root = x;
53}
54
55// kth: 1-indexed implicit position
56Node* kth(Node*& root, int k){
57    if (!root || k <= 0 || k > size(root)) return nullptr;
58    Node* cur = root; while (cur){
59        push(cur);
60        int ls = size(cur->l);
61        if (k <= ls) cur = cur->l;
62        else if (k == ls + 1) { splay(root, cur); return cur; }
63        else { k -= ls + 1; cur = cur->r; }
64    }
65    return nullptr;
66}
67
68// Expose interval [l, r] as root->r->l between two sentinels
69Node* expose(Node*& root, int l, int r){
70    Node* left = kth(root, l-1); // sentinel at l-1 to root
71    splay(root, left);
72    Node* right = kth(root, r+1); // sentinel at r+1 to be root->r
73    splay(root, right, root); // splay under root so that right is root->r
74    return right->l; // middle subtree
75}
76
77void reverse_range(Node*& root, int l, int r){ if (l>r) return; Node* mid = expose(root, l, r); if(!mid) return; mid->rev ^= 1; }
78
79void inorder_collect(Node* x, vector<int>& out){ if(!x) return; push(x); inorder_collect(x->l, out); out.push_back(x->val); inorder_collect(x->r, out); }
80
81// Build a balanced tree from vector vals (without sentinels)
82Node* build_balanced(const vector<int>& a, int l, int r){ if(l>r) return nullptr; int m=(l+r)/2; Node* x = new Node(a[m]); x->l = build_balanced(a, l, m-1); if(x->l) x->l->p = x; x->r = build_balanced(a, m+1, r); if(x->r) x->r->p = x; pull(x); return x; }
83
84int main(){
85    ios::sync_with_stdio(false); cin.tie(nullptr);
86
87    // Build initial sequence [1..8] with two sentinels at ends
88    vector<int> vals = {1,2,3,4,5,6,7,8};
89    Node* root = nullptr;
90    Node* L = new Node(INT_MIN); // left sentinel
91    Node* R = new Node(INT_MAX); // right sentinel
92    Node* mid = build_balanced(vals, 0, (int)vals.size()-1);
93    // Link: L as root, mid as L->r, R as rightmost
94    root = L; root->r = mid; if (mid) mid->p = root; pull(root);
95    // Attach R
96    // splay to rightmost and attach R
97    Node* cur = root; while(cur->r) cur = cur->r; splay(root, cur);
98    root->r = R; R->p = root; pull(root);
99
100    // Reverse range [3, 6]
101    reverse_range(root, 3, 6);
102
103    // Collect sequence excluding sentinels
104    vector<int> out; inorder_collect(root, out);
105    // strip sentinels
106    vector<int> filtered; for(int x: out) if(x!=INT_MIN && x!=INT_MAX) filtered.push_back(x);
107    cout << "Sequence after reverse [3,6]:";
108    for (int x: filtered) cout << ' ' << x; cout << '\n';
109
110    // Another operation: reverse [2, 7]
111    reverse_range(root, 2, 7);
112    out.clear(); inorder_collect(root, out); filtered.clear();
113    for(int x: out) if(x!=INT_MIN && x!=INT_MAX) filtered.push_back(x);
114    cout << "Sequence after reverse [2,7]:";
115    for (int x: filtered) cout << ' ' << x; cout << '\n';
116
117    return 0;
118}
119

This program builds an implicit-key splay tree representing a sequence with two sentinels (left and right boundaries). It supports reversing any subarray [l, r] by exposing the interval with two splays and toggling a lazy reverse flag on the middle subtree. The push function ensures that pending reversals are applied before rotations or traversals.

Time: Amortized O(log n) per reverse (two splays and O(1) tag flip)Space: O(n) storage; O(1) auxiliary per operation