v. Treaps and Balanced BSTs

A treap is a BST on keys and a heap on random priorities, so it has expected depth $O(\log n)$ with no balancing code. Everything is built from split and merge. Keyed by position (implicit treap), it becomes an array that supports insert, delete, reverse and move of ranges, which segment trees can’t do.

Proof: a treap on $n$ keys has expected depth $O(\log n)$

Fix a node $x$ at rank $r$ among the $n$ keys (sorted order), and for another node $y$ at rank $r^{\prime }\ne r$, $y$ is an ancestor of $x$ in the treap iff $y$ has the strictly largest priority among all nodes whose rank lies between $r$ and $r^{\prime }$ inclusive — because the treap’s structure is exactly: the maximum-priority node among any contiguous rank range is the root of that range’s subtree, and it is an ancestor of every other node in the range. With $|r-r^{\prime }|+1$ nodes in that range and priorities i.i.d. random, the probability $y$‘s priority is the unique maximum among them is $\frac{1}{|r-r^{\prime }|+1}$. So $E[\text{depth}(x)]={\sum }_{r^{\prime }\ne r}\mathrm{Pr}[y_{r^{\prime }}\text{ ancestor of }x]={\sum }_{k=1}^{n-1-r}\frac{1}{k+1}+{\sum }_{k=1}^r\frac{1}{k+1}\le 2H_n=O(\log n)$ (splitting into ranks above and below $r$, each a harmonic sum). Since this bound is uniform over $x$, the expected height of the whole tree is $O(\log n)$ by a union bound / linearity argument over all $n$ nodes. $■$

Proof: split/merge preserve the treap invariants (BST by key, heap by priority)

split(x, k, a, b) recurses on whichever child’s subtree straddles the size-$k$ boundary, reattaching the other side intact; since the original subtree was a valid treap, both a and b inherit a contiguous range of keys/positions from it (the invariant “BST order” survives because splitting only ever cuts along a key/size boundary, never reorders existing parent-child relationships among kept nodes) and the heap property survives because every node keeps the same set of ancestors it had minus the ones that got pulled into the other output, which were already smaller-priority ancestors by construction — no node’s priority relative to its surviving ancestors changes. merge(a, b) (with every key in $a$ less than every key in $b$, or sizes used as keys) always makes the higher-priority root of $\{a,b\}$ the new root — preserving the heap property at the top — and recurses on merge with the other tree threaded into the correct child (right child of $a$ if $a$‘s root wins, since $b$‘s keys are all larger; symmetric otherwise), which by induction returns a valid treap satisfying both the BST order (all of $a$‘s keys still precede all of $b$‘s) and heap order. $■$

Implicit treap with lazy reverse, add and range sums

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
struct Node { int l = 0, r = 0, sz = 1; unsigned pr; ll val, sum, add = 0; bool rev = false; };
vector<Node> t(1);                               // t[0] is the null node (sz 0)
int make(ll v) { Node x; x.pr = rng(); x.val = x.sum = v; t.push_back(x); return sz(t) - 1; }
void apply(int x, ll a, bool r) {
    if (!x) return;
    t[x].val += a; t[x].sum += a * t[x].sz; t[x].add += a;
    if (r) swap(t[x].l, t[x].r), t[x].rev ^= 1;
}
void push(int x) { if (t[x].add || t[x].rev) apply(t[x].l, t[x].add, t[x].rev), apply(t[x].r, t[x].add, t[x].rev), t[x].add = 0, t[x].rev = false; }
void pull(int x) { t[x].sz = 1 + t[t[x].l].sz + t[t[x].r].sz; t[x].sum = t[x].val + t[t[x].l].sum + t[t[x].r].sum; }
void split(int x, int k, int& a, int& b) {        // first k elements -> a, rest -> b
    if (!x) { a = b = 0; return; }
    push(x);
    if (t[t[x].l].sz < k) split(t[x].r, k - t[t[x].l].sz - 1, t[x].r, b), a = x;
    else split(t[x].l, k, a, t[x].l), b = x;
    pull(x);
}
int merge(int a, int b) {
    if (!a || !b) return a ^ b;
    if (t[a].pr > t[b].pr) { push(a); t[a].r = merge(t[a].r, b); pull(a); return a; }
    push(b); t[b].l = merge(a, t[b].l); pull(b); return b;
}
// operate on [l, r): split into A | B | C, modify B, merge back
template<class F> void onRange(int& root, int l, int r, F f) {
    int a, b, c; split(root, l, a, b); split(b, r - l, b, c); f(b); root = merge(merge(a, b), c);
}

Operation	How
insert at position $p$	split at $p$, merge left, new node, right
erase $[l,r)$	split out the middle and drop it
reverse $[l,r)$	apply(mid, 0, true)
range add / range sum	lazy tag / subtree aggregate
cyclic shift of $[l,r)$ by $k$	split into three parts and merge them in rotated order
move a block elsewhere, swap two blocks	split and merge in the new order
$k$-th element, position of a node	descend by sizes / walk up with parent pointers

Reach for the implicit treap specifically when a problem changes the length or order of the sequence — “move $[l,r]$ to the front”, “reverse $[l,r]$ then answer a range query”, “insert at position $p$”, “delete a range then keep querying”, a text editor with undo (make it persistent) — since a segment tree assumes a fixed set of positions and cannot do any of these.

Keyed (non-implicit) treaps split by key instead of size. Pass a key comparison in split, and it gives an ordered multiset with any augmentation you like (sum of the $k$ smallest, max in a key range).

Union of two keyed treaps with interleaved keys runs in $O(m\log (n/m))$ expected (a known but non-trivial result for randomized treap union — the recursion splits the larger treap by each node of the smaller one’s path, and bounding the total split work needs a careful accounting of how priorities interleave; not rederived here):

int unite(int a, int b) {                         // keyed treap; splitByKey(x, key, l, r): keys < key go left
    if (!a || !b) return a ^ b;
    if (t[a].pr < t[b].pr) swap(a, b);
    int L, R; splitByKey(b, t[a].val, L, R);
    t[a].l = unite(t[a].l, L); t[a].r = unite(t[a].r, R); pull(a);
    return a;
}

Persistent treap: copy each node before modifying it in split/merge (and in push, since children change). That gives versioned arrays, “copy a range and paste it” with $O(\log n)$ cost, and undo history. With copy-paste operations, the random priorities become correlated, so use the “merge by random choice proportional to sizes” variant (choose a as root with probability $\frac{|a|}{|a|+|b|}$) instead of stored priorities.

Practical: preallocate the node array (t.reserve), use iterative pointers or indices, and expect a treap to be about 3-5x slower than a segment tree for the same job. Seed the RNG from chrono::steady_clock — a fixed seed is hackable on Codeforces. Recursion depth is $O(\log n)$ expected but can spike occasionally; for $n=10^6$ this is still fine in practice.

Choosing a balanced BST

Tree	Height	Notes
treap	expected $O(\log n)$	easiest to write; split/merge; persistent-friendly
splay	amortized $O(\log n)$	moves accessed nodes to the root; the engine of link-cut trees (Link-Cut Tree)
red-black (std::set)	$\le 2{\log }_2(n+1)$	what the STL gives; can’t be augmented directly
PBDS tree	$\le 2{\log }_2(n+1)$	order statistics for free (PBDS)
AVL	$\le 1.44{\log }_{2}n$	deterministic, strictest balance, fastest lookups, more rotations than red-black
weight-balanced (WBLT)	$O(\log n)$	popular for persistent sequences (no randomness, merge by sizes)
scapegoat	amortized $O(\log n)$	rebuild unbalanced subtrees; no per-node balance data; useful when nodes carry heavy structures (KD-tree insertions)
B-tree / B+-tree	$O({\log }_{B}n)$	many keys per node, built for disk/cache locality rather than comparisons — every database uses one, essentially never hand-written in CP
skip list	expected $O(\log n)$	probabilistic linked levels; mostly of theoretical interest in CP (proof below)

Proof: AVL height is $O(\log n)$, specifically $\le 1.44{\log }_{2}n$

Let $N(h)$ be the minimum number of nodes in an AVL tree of height $h$. The sparsest such tree has one child of height $h-1$ (itself minimal) and the other of height $h-2$ (also minimal, the maximum height difference the invariant allows), plus the root: $N(h)=N(h-1)+N(h-2)+1$, with $N(0)=1,N(-1)=0$. This is the Fibonacci recurrence shifted by a constant; solving (or just noting $N(h)+1$ satisfies the pure Fibonacci recurrence with the same growth rate) gives $N(h)=\Theta ({\phi }^h)$ where $\phi =\frac{1+\sqrt{5}}{2}\approx 1.618$. So a tree with $n$ nodes and height $h$ satisfies $n\ge N(h)=\Omega ({\phi }^h)$, giving $h=O({\log }_{\phi }n)=O(\log n/\log \phi )\approx 1.44{\log }_{2}n$. $■$

Proof: red-black height is $\le 2{\log }_2(n+1)$

The red-black invariants (no red node has a red child; every root-to-null path has the same number of black nodes, the “black-height” $bh$) force every root-to-leaf path to have length $\le 2bh$ (at most one red node can be inserted between any two consecutive black nodes on a path, by the no-two-reds-in-a-row rule). Separately, a subtree with black-height $bh$ has at least $2^{bh}-1$ internal nodes (by induction: collapsing every red node into its black parent gives an ordinary binary tree where every root-to-leaf path has exactly $bh$ black nodes, which has $\ge 2^{bh}-1$ nodes by the standard binary-tree node-count bound). So $n\ge 2^{bh}-1$, giving $bh\le {\log }_2(n+1)$, and height $\le 2bh\le 2{\log }_2(n+1)$. $■$

If you need a balanced BST you can extend — with subtree aggregates, lazy propagation, split and merge — write a treap: it is 40 lines, the balancing is a coin flip, and split/merge make range operations trivial. Splay trees are the alternative when you need the access locality property or are building link-cut trees. AVL, red-black and B-trees are worth understanding but almost never worth implementing from scratch in a contest.

Two classic std::set/multiset bugs

1. multiset::erase(value) erases every copy. Use erase(find(value)) to remove one.
2. std::lower_bound(s.begin(), s.end(), x) on a set is $O(n)$ — the iterators are not random access. Always use the member function s.lower_bound(x).

Skip list

A probabilistic ordered set built from linked lists with random levels: each key gets a tower of height $h$ with $\mathrm{Pr}[h>k]=2^{-k}$, and a search descends from the top level, moving right while the next key is still smaller. Expected $O(\log n)$ insert/erase/search/lower_bound, expected $O(n)$ memory; duplicates are kept (erase removes one copy). Mostly of theoretical interest in CP — a treap or std::set dominates it in practice.

Proof: skip list search is $O(\log n)$ expected

With $\mathrm{Pr}[\text{tower height}>k]=2^{-k}$, the expected number of nodes with tower height $\ge k$ among $n$ keys is $n\cdot 2^{-k}$; setting this to $O(1)$ gives the expected top level in use at $k={\log }_{2}n$, so there are $O(\log n)$ levels. A search descends level by level; at each level it moves right only while the next key is still smaller, and standard analysis (run the search backwards, from the found position up to the top: at each level, the node is reached either by moving up from the level below, or by moving left — and the probability of moving left at any given step is bounded by a constant since a left-move only happens when the current node does not have a tower extending to the next level up, probability $\le \frac{1}{2}$) shows the expected number of moves at each level is $O(1)$, giving $O(\log n)$ expected total moves across $O(\log n)$ levels. Expected memory is ${\sum }_{\text{keys}}E[\text{tower height}]={\sum }_{\text{keys}}{\sum }_{k\ge 0}\mathrm{Pr}[\text{height}>k]=n{\sum }_{k\ge 0}{2}^{-k}=O(n)$. $■$

Splay tree in one paragraph

Each access rotates the node to the root with zig-zig/zig-zag steps. With potential $\sum \log (\text{size})$, the amortized cost of an access is $O(\log n)$ (access lemma). Implicit splay trees do everything implicit treaps do.

Proof (cited): the splay tree access lemma

With potential $\Phi ={\sum }_v{\log }_2(\text{size}(v))$ (sum over all nodes of the log of their subtree size), Sleator and Tarjan’s access lemma (1985) shows each zig-zig/zig-zag step’s amortized cost (actual rotation cost plus the change in $\Phi$) is $O(1+\log \frac{\text{size}(v)\text{ after}}{\text{size}(v)\text{ before}})$, and telescoping over the whole splay from a leaf to the root collapses to $O(\log n)$ total amortized cost per access — a correct but intricate argument (case analysis on zig/zig-zig/zig-zag) not reproduced in full here. In practice they’re used where the “move to root” property matters: link-cut trees, and dynamic sequences with strong locality of access. Rotation code:

// ch[x][0/1] children, fa[x] parent; rotate x above its parent
void rotate(int x) {
    int y = fa[x], z = fa[y], k = ch[y][1] == x;
    if (z) ch[z][ch[z][1] == y] = x;
    fa[x] = z; ch[y][k] = ch[x][!k]; if (ch[x][!k]) fa[ch[x][!k]] = y;
    ch[x][!k] = y; fa[y] = x; pull(y); pull(x);
}
void splay(int x, int goal = 0) {                 // push lazies from the root down to x first
    while (fa[x] != goal) {
        int y = fa[x], z = fa[y];
        if (z != goal) rotate((ch[z][1] == y) == (ch[y][1] == x) ? y : x);
        rotate(x);
    }
}

Cartesian tree

The treap of (index, value) pairs: built in $O(n)$ with a monotonic stack (construction and correctness proved in Monotonic Stack), root at the minimum, in-order traversal = the array order. RMQ is LCA in it. Equal values: break ties consistently (e.g. the leftmost occurrence becomes the ancestor) so the tree is well-defined. Depth can be $\Theta (n)$ on adversarial input (a sorted array), so traverse it iteratively rather than recursively.