Splay trees are self-adjusting binary search trees where each accessed node is rotated to the root through a sequence of tree rotations. Although the initial structure satisfies BST ordering, intermediate states may not, yet the in-order traversal remains consistent.

Rotation Mechanics

Rotations follow the same scheme as Treaps: zig (single rotation) and zig-zig or zig-zag patterns depending on node alignment relative to its parent and grandparent.

Core Principle

Every operation moves the target node to the root via splay, ensuring amortized (O(\log n)) time per operation due to potential energy-based analysis.

Splay Operation Details

splay(x, k) relocates node x just below node k. Two cases apply:

• Collinear case (node x is a straight-line descendant from k): Rotate parent y then x. This moves x up two levels per iteration.
• Non-collinear case (an angle exists between x, parent y, and grandparent z): Rotate x twice appropriately.

Correct rotation selection is essential for preserving logarithmic complexity.

Implementation uses iterative ascent, applying rotations until x becomes a direct child of k. If k is null, x becomes root.

Basic Operations

Insertion

Insert normally as in BST, placing at a leaf, then splay it to root. For inserting a batch after node y: locate successor z, splay y to root, splay z below y; z's left subtree will be empty, suitable for attaching the new sequence.

Deletion of a Range

To remove [l, r], locate predecessor l-1 and successor r+1. Splay l-1 to root, then splay r+1 below it; r+1's left subtree corresponds exactly to [l, r] and can be detached.

Other operations mirror those of standard balanced trees.

Maintaining Auxiliary Data

• Subtree size enables k-th element queries:
  updateSize(t) = size(left) + size(right) + 1 performed after every structural change.
• Lazy reversal tags facilitate range reversals:
  Before recursion, propagate flag: swap children and toggle their flags, then clear current node's flag.

Example Structure

struct Node {
    int ch[2], parent, val, lazyRev, sz;
    void setup(int v, int par) {
        val = v; parent = par;
        sz = 1; lazyRev = 0;
        ch[0] = ch[1] = 0;
    }
} tree[MAXN];

class SplayTree {
    int root, nodeCnt;

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

    void push(int x) {
        if (tree[x].lazyRev) {
            swap(tree[x].ch[0], tree[x].ch[1]);
            if (tree[x].ch[0]) tree[tree[x].ch[0]].lazyRev ^= 1;
            if (tree[x].ch[1]) tree[tree[x].ch[1]].lazyRev ^= 1;
            tree[x].lazyRev = 0;
        }
    }

    void rot(int x) {
        int y = tree[x].parent, z = tree[y].parent;
        int side = tree[y].ch[1] == x;
        tree[z].ch[tree[z].ch[1] == y] = x;
        tree[x].parent = z;
        tree[y].ch[side] = tree[x].ch[!side];
        if (tree[x].ch[!side]) tree[tree[x].ch[!side]].parent = y;
        tree[x].ch[!side] = y;
        tree[y].parent = x;
        update(y); update(x);
    }

    void splay(int x, int stop) {
        while (tree[x].parent != stop) {
            int y = tree[x].parent, z = tree[y].parent;
            if (z != stop)
                ((tree[y].ch[1] == x) ^ (tree[z].ch[1] == y)) ? rot(x) : rot(y);
            rot(x);
        }
        if (!stop) root = x;
    }

public:
    SplayTree() : root(0), nodeCnt(0) {}

    void add(int val) {
        int cur = root, prev = 0;
        while (cur) {
            prev = cur;
            cur = tree[cur].ch[val > tree[cur].val];
        }
        cur = ++nodeCnt;
        if (prev) tree[prev].ch[val > tree[prev].val] = cur;
        tree[cur].setup(val, prev);
        splay(cur, 0);
    }

    int kth(int rank) {
        int cur = root;
        while (true) {
            push(cur);
            int lsz = tree[tree[cur].ch[0]].sz;
            if (lsz >= rank) cur = tree[cur].ch[0];
            else if (lsz + 1 == rank) return cur;
            else rank -= lsz + 1, cur = tree[cur].ch[1];
        }
    }
};

Application Scenarios

Range Reversal (Sequence Flip)

Maintain an array virtually via in-order positions. Use lazy reversal tags on subtrees representing segments. Split at boundaries, flip the segment’s root flag, and merge back. Complexity stays logarithmic per operation.

K-th Statistics in Dynamic Set

With subtree sizes maintained, finding k-th smallest is straightforward: descend while comparing rank with left-subtree size.

Merging Disjoint Sets Heuristically

When combining two splay trees representing sets, use size heuristic: always merge smaller into larger to bound total cost to (O(n \log^2 n)). Transfer elements individually with insertion and splaying.

Memory Recycling

Reuse removed nodes by keeping a free list. On deletion, push index to stack; on insertion, pop from stack instead of incrementing counter, reducing allocation overhead.

Advanced Maintenance

For problems requiring aggregate data (sum, max prefix/suffix/total), extend node structure with fields like sum, maxPrefix, maxSuffix, maxSubarray. Update these during pushup and handle propagation in pushdown for both reversal and assignment operations.