Treap and Implicit Treap

A treap is a binary search tree by key and a heap by a random priority. Because the priorities are random, the tree is a random BST, so its expected height is $O(\log n)$ — with no rotations to balance, no colours, and no height bookkeeping.

Split and merge — the whole structure

Everything is built from two operations.

struct Node {
    int key, prio, sz = 1;
    Node *l = nullptr, *r = nullptr;
    Node(int k) : key(k), prio(rng()) {}
};
 
int size(Node* t) { return t ? t->sz : 0; }
void pull(Node* t) { if (t) t->sz = 1 + size(t->l) + size(t->r); }
 
// split by key: L holds keys < k, R holds keys >= k
void split(Node* t, int k, Node*& L, Node*& R) {
    if (!t) { L = R = nullptr; return; }
    if (t->key < k) { split(t->r, k, t->r, R); L = t; }
    else            { split(t->l, k, L, t->l); R = t; }
    pull(t);
}
 
// merge: every key in a is < every key in b
Node* merge(Node* a, Node* b) {
    if (!a || !b) return a ? a : b;
    if (a->prio > b->prio) { a->r = merge(a->r, b); pull(a); return a; }
    else                   { b->l = merge(a, b->l); pull(b); return b; }
}
 
void insert(Node*& t, int k) {
    Node *L, *R;
    split(t, k, L, R);
    t = merge(merge(L, new Node(k)), R);
}
void erase(Node*& t, int k) {
    Node *L, *M, *R;
    split(t, k, L, R); split(R, k + 1, M, R);
    t = merge(L, R);                                  // M is discarded
}

split and merge are each $O(\log n)$ expected, and every other operation is two or three of them.

Implicit treap — a treap keyed by position

Drop the key and use subtree size as the implicit index. The treap now represents a sequence, and it supports operations no array or segment tree can:

// split the first k elements into L, the rest into R
void split(Node* t, int k, Node*& L, Node*& R) {
    if (!t) { L = R = nullptr; return; }
    push(t);
    if (size(t->l) < k) { split(t->r, k - size(t->l) - 1, t->r, R); L = t; }
    else                { split(t->l, k, L, t->l); R = t; }
    pull(t);
}

Operation	How
Insert at position $p$	split at $p$, merge with a new node
Erase position $p$	split twice, discard the middle
Reverse $[l,r]$	split out the range, set a lazy rev flag
Cyclic shift $[l,r]$	split into three, reorder, merge
Move $[l,r]$ to position $p$	split out and re-merge elsewhere
Range sum/min/max	subtree aggregate, pulled on merge
Range add/assign	lazy tags, pushed on split
Concatenate two sequences	one merge
$k$-th element	descend by subtree size

The lazy machinery is exactly the same as a lazy segment tree — push before descending, pull after returning.

void push(Node* t) {
    if (!t || !t->rev) return;
    t->rev = false;
    swap(t->l, t->r);
    if (t->l) t->l->rev ^= 1;
    if (t->r) t->r->rev ^= 1;
}

When the implicit treap is the only tool

Reach for it when the problem changes the length or order of the sequence:

• “Move the subarray $[l,r]$ to the front”
• “Reverse $[l,r]$, then answer a range query”
• “Insert a value at position $p$”
• “Delete a range, then keep querying”
• Text editors with undo (make it persistent)

A segment tree cannot do any of these, because it assumes a fixed set of positions.

Merging two treaps with interleaved keys

merge requires all keys of the first to be less than all keys of the second. To union two arbitrary treaps, use the recursive unite:

Node* unite(Node* a, Node* b) {
    if (!a || !b) return a ? a : b;
    if (a->prio < b->prio) swap(a, b);
    Node *L, *R;
    split(b, a->key, L, R);
    a->l = unite(a->l, L);
    a->r = unite(a->r, R);
    pull(a);
    return a;
}

$O(m\log (n/m))$ for treaps of sizes $m\le n$ — the information-theoretic optimum, and the same bound small-to-large merging achieves.

Practical notes

• Use a good RNG: mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()). A fixed seed is hackable.
• Recursion depth is $O(\log n)$ expected but can spike; for $n=10^6$ this is still fine.
• Allocate nodes from a preallocated array rather than new — a 2-3× speedup.
• Persistent treaps come almost free: copy a node instead of mutating it in split/merge.

See also: Balanced BSTs · Lazy Propagation · Persistent Structures