Cartesian Tree (Treap)

Quick Revisit: A BST by key that simultaneously satisfies the heap property by a secondary random priority—a treap. Two primitives, split and merge, run in $O(\log n)$ expected and compose into everything: insert, delete, range queries, even reverse. The implicit variant replaces explicit keys with subtree sizes, turning the treap into a full sequence data structure. The classic trap: forgetting to recompute subtree size (or aggregate) after split/merge—the tree still looks valid but ranks and range answers are silently wrong. (Practice problems)

Difficulty: CF 1900–2300 · Prereqs: Segment Tree, Priority Queue and Heaps

---

Contents

• Why This Exists
• Under the Hood
• C++ STL Reference
• Implementation
• Operations Reference
• Problem Patterns
• Contest Cheat Sheet
• Gotchas & Debugging
• Can You...
• Practice Problems
• Further Reading

---

A Cartesian tree is the structure you reach for when a sequence must be both searchable by key and ordered by priority simultaneously. The BST side gives you key order; the heap side lifts the best priority to the root. When priorities are random, the same object is called a treap (tree + heap). Replace explicit keys with subtree sizes and the tree becomes a mutable sequence structure that supports $O(\log n)$ split, merge, insert, delete, reverse, and range queries—everything a segment tree does, plus structural mutations.

---

Why This Exists

You have 7 items, each with a key (for lookup) and a priority (for scheduling):

  key:      10   20   30   40   50   60   70
  priority:  5    2    8    1    6    3    7

You need two operations to be fast:

1. Search by key—find the item with key 30.
2. Find min-priority—which item is most urgent?

Attempt 1: BST on keys.

Build a balanced BST ordered by key:

             (40)
            /    \
         (20)    (60)
         /  \    /  \
      (10) (30)(50) (70)

Search for key 30? Walk left from 40, right from 20—found in 3 steps. $O(\log n)$. Good.

Find the item with minimum priority (priority 1, which belongs to key 40)? The BST is sorted by key, not priority. We must visit every node to check priorities: 7 comparisons for 7 elements. $O(n)$. Terrible.

Attempt 2: Min-heap on priorities.

Build a min-heap ordered by priority:

               (40,pri=1)
              /          \
        (20,pri=2)     (60,pri=3)
        /       \       /       \
   (10,pri=5)(30,pri=8)(50,pri=6)(70,pri=7)

Find min-priority? It is the root—$O(1)$. Good.

Search for key 30? Heaps have no key ordering. We check the root (key 40—not it), then its children (keys 20, 60), then their children. In the worst case we scan all 7 nodes. $O(n)$. Terrible.

The damage. With $n={10}^5$ items and ${10}^5$ mixed queries:

  +----------------+-----------------+--------------------+------------------+
  | Approach       | Search by key   | Find min-priority  | Total worst case |
  +----------------+-----------------+--------------------+------------------+
  | BST only       | O(log n)/query  | O(n) per query     | ~10^10 ops       |
  | Heap only      | O(n) per query  | O(1) per query     | ~10^10 ops       |
  +----------------+-----------------+--------------------+------------------+

Either way, one operation costs $O(n)$ per query—you end up scanning the entire structure on every call. There has to be a way to get $O(\log n)$ for both.

The fix is to stop treating lookup and priority as separate problems. Build one binary tree where keys follow BST order (left < root < right) and priorities follow heap order (parent priority $\le$ child priority). That single shape answers both operations in logarithmic time, and the tree is uniquely determined by the data. This structure is a Cartesian tree. When priorities are chosen randomly, it is called a treap (tree + heap), and its expected height is $O(\log n)$—equivalent to a randomly built BST, but without needing to insert in random order.

Analogy: Think of a company org chart. Employees are listed alphabetically (BST on name—binary-search for anyone by name), but the reporting hierarchy follows seniority (heap on years of service—the most senior person is CEO at the root, and every manager outranks their direct reports). Once you know everyone's name and seniority, the org chart is completely forced. No ambiguity.

Where the analogy breaks: in a real org chart, one manager can have many direct reports. In a Cartesian tree, every node has at most two children—it is a binary tree. The "alphabetical order" constraint manifests as the in-order traversal sequence, not a spatial arrangement on a wall.

Walkthrough

Take the same 7 items. The key construction trick is stack-based and $O(n)$: process items left to right in key order, keep the rightmost path of the tree on a stack, and let each new item absorb the lower-priority nodes it needs to sit above.

Algorithm: For each new item, pop nodes from the stack whose priority is worse (larger, for min-heap) than the new item's priority. The last popped node becomes the new item's left child. The new item then becomes the right child of whatever remains on top of the stack.

  key:      10   20   30   40   50   60   70
  priority:  5    2    8    1    6    3    7
  index:     0    1    2    3    4    5    6

Step 1: Process (key=10, pri=5)

Stack is empty. Push (10,5). It becomes the root.

  Stack: [ (10,5) ]

  Tree:   (10,5)

Step 2: Process (key=20, pri=2)

Top of stack is (10,5). Priority 5 > 2, so pop (10,5). (10,5) becomes the left child of (20,2). Stack was empty underneath, so (20,2) is the new root. Push (20,2).

  Stack: [ (20,2) ]

  Tree:     (20,2)
            /
        (10,5)

Heap check: 2 ≤ 5. BST check: in-order gives 10, 20.

Step 3: Process (key=30, pri=8)

Top of stack is (20,2). Priority 2 < 8, so do NOT pop. (30,8) becomes right child of (20,2). Push (30,8).

  Stack: [ (20,2), (30,8) ]

  Tree:     (20,2)
            /    \
        (10,5)  (30,8)

Heap check: 2 ≤ 5, 2 ≤ 8. In-order: 10, 20, 30.

Step 4: Process (key=40, pri=1)

Top is (30,8). Priority 8 > 1, pop (30,8). Top is (20,2). Priority 2 > 1, pop (20,2). Stack is now empty. The last popped node was (20,2)—the entire subtree rooted at (20,2) becomes the left child of (40,1). (40,1) is the new root.

  Stack: [ (40,1) ]

  Tree:         (40,1)
                /
            (20,2)
            /    \
        (10,5)  (30,8)

Heap check: 1 ≤ 2, 2 ≤ 5, 2 ≤ 8. In-order: 10, 20, 30, 40.

Step 5: Process (key=50, pri=6)

Top is (40,1). Priority 1 < 6, do NOT pop. (50,6) becomes right child of (40,1). Push (50,6).

  Stack: [ (40,1), (50,6) ]

  Tree:         (40,1)
                /    \
            (20,2)  (50,6)
            /    \
        (10,5)  (30,8)

Step 6: Process (key=60, pri=3)

Top is (50,6). Priority 6 > 3, pop (50,6). (50,6) becomes left child of (60,3). Top is (40,1). Priority 1 < 3, do NOT pop. (60,3) becomes right child of (40,1). Push (60,3).

  Stack: [ (40,1), (60,3) ]

  Tree:         (40,1)
                /    \
            (20,2)  (60,3)
            /    \   /
        (10,5) (30,8)(50,6)

Step 7: Process (key=70, pri=7)

Top is (60,3). Priority 3 < 7, do NOT pop. (70,7) becomes right child of (60,3). Push (70,7).

  Stack: [ (40,1), (60,3), (70,7) ]

  Tree:         (40,1)
                /    \
            (20,2)  (60,3)
            /    \   /   \
        (10,5) (30,8)(50,6)(70,7)

Final verification:

  In-order traversal: 10, 20, 30, 40, 50, 60, 70   <- BST order by key

  Heap check (parent priority <= child priority):
    (40, pri=1) is root -- priority 1 is the global minimum
    (40,1) -> children (20,2), (60,3):  1 <= 2, 1 <= 3
    (20,2) -> children (10,5), (30,8):  2 <= 5, 2 <= 8
    (60,3) -> children (50,6), (70,7):  3 <= 6, 3 <= 7

Consolidated stack view—every step in one picture:

  Step │ Insert   │ Stack (bottom -> top)             │ Pops │ Left-child attachment
  ─────┼──────────┼──────────────────────────────────┼──────┼──────────────────────────
    1  │ (10, 5)  │ (10,5)                           │  0   │ --
    2  │ (20, 2)  │ (20,2)                           │  1   │ (10,5) -> left of (20,2)
    3  │ (30, 8)  │ (20,2) (30,8)                    │  0   │ --
    4  │ (40, 1)  │ (40,1)                           │  2   │ (20,2) subtree -> left of (40,1)
    5  │ (50, 6)  │ (40,1) (50,6)                    │  0   │ --
    6  │ (60, 3)  │ (40,1) (60,3)                    │  1   │ (50,6) -> left of (60,3)
    7  │ (70, 7)  │ (40,1) (60,3) (70,7)             │  0   │ --
  ─────┴──────────┴──────────────────────────────────┴──────┴──────────────────────────
  Total pushes: 7 (each element pushed exactly once)
  Total pops:   4 (each element popped at most once)
  Total ops:   11 = O(n)

The stack always holds the rightmost path of the tree, from root down to the rightmost leaf. Each new element either extends this path (pushed on top) or shortens it first (pops nodes with worse priority), then extends it. Since each of the $n$ elements is pushed and popped at most once, the total work is $O(n)$—not $O(n\log n)$, and certainly not $O(n^2)$.

Operation count: We processed 7 items. Each item is pushed exactly once and popped at most once, for at most $2\times 7=14$ stack operations—$O(n)$ overall. Compare this with inserting one-by-one into a balanced BST with rotations: $O(n\log n)$.

On the finished tree, both operations run fast:

• Search by key 30: Walk from root (40) left to (20), right to (30). Found in 3 steps—$O(\log n)$.
• Find min-priority: Read the root (40, priority 1). Done in 1 step—$O(1)$.

Both fast simultaneously—the dual BST/heap structure makes this possible. Here is the property that guarantees it.

The Invariant

+------------------------------------------------------------------+
| INVARIANT (Cartesian Tree / Treap):                              |
|                                                                  |
| 1. In-order traversal of the tree produces keys in sorted order  |
|    (BST property on keys).                                       |
|                                                                  |
| 2. For every node, parent priority <= child priority             |
|    (min-heap property on priorities).                            |
|                                                                  |
| Together these two constraints uniquely determine the tree       |
| shape for any set of (key, priority) pairs with distinct         |
| priorities.                                                      |
+------------------------------------------------------------------+

Why it holds: The stack-based construction preserves both properties at every step. Popping a node off the stack and making it the left child of the new node maintains BST order (the popped node has a smaller key and now sits in the left subtree) and heap order (the popped node had worse priority, so it belongs below the new node).

Connect to the walkthrough: In Step 4, when (40, pri=1) arrives, we pop (30,8) and (20,2) because both have priority > 1. The entire subtree rooted at (20,2) becomes the left child of (40,1). If we had not popped—if (40,1) sat below (20,2)—the min-heap invariant would break: priority 1 < 2, but the child would have lower priority than the parent. The pop is exactly what keeps the invariant alive.

For treaps (random priorities): When priorities are drawn uniformly at random, the resulting Cartesian tree is structurally equivalent to a random BST—expected height $O(\log n)$. This gives a balanced BST without explicit rotations, and every operation (split, merge, insert, delete) runs in $O(\log n)$ expected time.

For implicit treaps: Replace explicit keys with implicit positions computed from subtree sizes. The in-order traversal still defines sequence order. This turns the treap into a mutable sequence data structure supporting $O(\log n)$ split, merge, insert-at-position, delete-at-position, reverse, and range queries—everything a segment tree does, plus structural mutations.

Split/Merge paradigm. Every operation on an implicit treap reduces to two primitives:

• split(t, k)—split tree t into first $k$ elements and the rest.
• merge(l, r)—merge two trees where all keys in l precede all keys in r.

Insert = split + merge new node + merge. Delete = split around target + merge the rest. Range query = split out the range, query, merge back.

Explicit vs. Implicit treap:

• Explicit: keys are actual values; BST ordered by value. Use when you need an ordered set/map with split-by-value.
• Implicit: keys are positions (array indices), computed on-the-fly from subtree sizes. Use when you need a mutable sequence.

This entry focuses on the implicit treap since it is far more common in contests.

---

Under the Hood

A few things the code alone won't tell you.

The dual property is the entire point. A Cartesian tree is not "just another heap." It simultaneously satisfies BST order on positions and heap order on values. Every structural property—uniqueness, LCA semantics, the $O(n)$ build—flows from this duality. Think only "heap" and you miss half the power.

RMQ ↔ LCA reduction. Build a Cartesian tree on array values (min-heap on values, BST on indices). Then range_min(l, r) equals the value at LCA(l, r) in the Cartesian tree. This is a deep structural fact: any RMQ problem can be converted to an LCA problem and vice versa. The Cartesian tree is the bridge.

  Array:    [5, 2, 8, 1, 6, 3, 7]
  Index:     0  1  2  3  4  5  6

  Cartesian tree (min-heap on values, BST on indices):

              (idx=3, val=1)         <- global min at index 3
             /               \
       (idx=1, val=2)   (idx=5, val=3)
       /          \      /          \
  (idx=0,val=5)(idx=2,val=8)(idx=4,val=6)(idx=6,val=7)

  range_min(0, 2) = value at LCA(index 0, index 2)
                   = value at index 1 = 2   (min of [5, 2, 8])
  range_min(4, 6) = value at LCA(index 4, index 6)
                   = value at index 5 = 3   (min of [6, 3, 7])

The $O(n)$ build is essential. The monotone-stack construction runs in $O(n)$. Naive insertion one-by-one into a BST/heap hybrid is $O(n^2)$ in the worst case (or $O(n\log n)$ with a balanced BST). For $n$ up to ${10}^6$, the linear build is what makes the Cartesian tree practical in competition. Without the stack trick, the structure is too slow to be useful.

Reach for this when you see "insert/delete at arbitrary position in $O(\log n)$" (implicit treap), "reverse a subarray" or "cut and paste" (implicit treap with lazy reversal), "split a sequence into two and merge two sequences" (split/merge primitives), or "balanced BST with order statistics" where __gnu_pbds isn't flexible enough (explicit treap). The RMQ↔LCA bridge is a second signal: if a problem suddenly wants LCA structure over a "minimum hierarchy," Cartesian tree is the right construction.

Don't reach for it when the problem involves a static array with point updates (a segment tree is simpler and faster by a constant factor), when you only need sorted-set insert/delete/find without split-by-position (use std::set or __gnu_pbds::tree), or when queries can be processed offline (Mo's algorithm or an offline segment tree wins—the treap's online flexibility is wasted on batch workloads). Pure RMQ on a static array belongs to sparse table, not Cartesian tree.

---

C++ STL Reference

There is no STL treap—the entire structure is hand-rolled.

std::set and std::map use red-black trees internally but expose no split/merge. The policy-based __gnu_pbds::tree gives order statistics but no split/merge or lazy propagation.

You implement from scratch. The upside: full control over lazy tags, custom aggregates, and persistence.

---

Implementation

Version A: Minimal Implicit Treap (Contest Template)

#include <bits/stdc++.h>
using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

struct Node {
    int val, pri, cnt;
    bool rev;
    long long sum;
    Node *l, *r;
    Node(int v) : val(v), pri(rng()), cnt(1), rev(false),
                  sum(v), l(nullptr), r(nullptr) {}
};

int cnt(Node* t) { return t ? t->cnt : 0; }
long long sum(Node* t) { return t ? t->sum : 0LL; }

void pull(Node* t) {
    if (t) {
        t->cnt = 1 + cnt(t->l) + cnt(t->r);
        t->sum = t->val + sum(t->l) + sum(t->r);
    }
}

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

void split(Node* t, int k, Node*& l, Node*& r) {
    if (!t) { l = r = nullptr; return; }
    push(t);
    if (cnt(t->l) < k) {
        split(t->r, k - cnt(t->l) - 1, t->r, r);
        l = t;
    } else {
        split(t->l, k, l, t->l);
        r = t;
    }
    pull(t);
}

void merge(Node*& t, Node* l, Node* r) {
    if (!l || !r) { t = l ? l : r; return; }
    push(l); push(r);
    if (l->pri > r->pri) {
        merge(l->r, l->r, r);
        t = l;
    } else {
        merge(r->l, l, r->l);
        t = r;
    }
    pull(t);
}

void insert(Node*& t, int pos, int val) {
    Node *l, *r;
    split(t, pos, l, r);
    Node* nd = new Node(val);
    merge(l, l, nd);
    merge(t, l, r);
}

void erase(Node*& t, int pos) {
    Node *l, *m, *r;
    split(t, pos, l, r);
    split(r, 1, m, r);
    delete m;
    merge(t, l, r);
}

void reverse(Node*& t, int l_pos, int r_pos) {
    Node *a, *b, *c;
    split(t, l_pos, a, b);
    split(b, r_pos - l_pos, b, c);
    b->rev ^= 1;
    merge(b, b, c);
    merge(t, a, b);
}

long long query_sum(Node*& t, int l_pos, int r_pos) {
    Node *a, *b, *c;
    split(t, l_pos, a, b);
    split(b, r_pos - l_pos, b, c);
    long long res = sum(b);
    merge(b, b, c);
    merge(t, a, b);
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;

    Node* root = nullptr;
    for (int i = 0; i < n; i++) {
        int x; cin >> x;
        insert(root, i, x);
    }

    while (q--) {
        int type; cin >> type;
        if (type == 1) {
            int pos, val; cin >> pos >> val;
            insert(root, pos, val);
        } else if (type == 2) {
            int pos; cin >> pos;
            erase(root, pos);
        } else if (type == 3) {
            int l, r; cin >> l >> r;
            reverse(root, l, r);
        } else {
            int l, r; cin >> l >> r;
            cout << query_sum(root, l, r) << "\n";
        }
    }
    return 0;
}

Version B: Verbose with Inline Comments + Range Assignment

#include <bits/stdc++.h>
using namespace std;

// Mersenne Twister seeded with high-res clock -- never use rand().
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

struct Node {
    int val, pri, cnt;
    long long sum;
    bool rev;           // lazy: reverse subtree
    int assign;         // lazy: assign value (-1 = no pending assignment)
    Node *l, *r;

    Node(int v)
        : val(v), pri(rng()), cnt(1), sum(v),
          rev(false), assign(-1), l(nullptr), r(nullptr) {}
};

// Safe accessors for null pointers.
int cnt(Node* t) { return t ? t->cnt : 0; }
long long gsum(Node* t) { return t ? t->sum : 0LL; }

// Recalculate aggregates from children. Call after any structural change.
void pull(Node* t) {
    if (!t) return;
    t->cnt = 1 + cnt(t->l) + cnt(t->r);
    t->sum = (long long)t->val + gsum(t->l) + gsum(t->r);
}

// Apply a pending assignment to a single node.
void apply_assign(Node* t, int v) {
    if (!t) return;
    t->val = v;
    t->sum = (long long)v * t->cnt;
    t->assign = v;
}

// Push lazy tags down to children before accessing them.
// ORDER MATTERS: apply assign before reverse (assign overwrites reverse).
void push(Node* t) {
    if (!t) return;

    // Push assignment first.
    if (t->assign != -1) {
        apply_assign(t->l, t->assign);
        apply_assign(t->r, t->assign);
        t->assign = -1;
    }

    // Push reversal.
    if (t->rev) {
        swap(t->l, t->r);
        if (t->l) t->l->rev ^= 1;
        if (t->r) t->r->rev ^= 1;
        t->rev = false;
    }
}

// Split first k elements into l, rest into r.
// All implicit-key operations use this: position = cnt(left subtree).
void split(Node* t, int k, Node*& l, Node*& r) {
    if (!t) { l = r = nullptr; return; }
    push(t);
    int left_size = cnt(t->l);
    if (left_size < k) {
        // Current node and its left subtree go to l.
        // Recurse into right subtree with remaining count.
        split(t->r, k - left_size - 1, t->r, r);
        l = t;
    } else {
        // Current node goes to r.
        // Recurse into left subtree.
        split(t->l, k, l, t->l);
        r = t;
    }
    pull(t);
}

// Merge two treaps where all keys in l precede all keys in r.
// The node with higher priority becomes the root.
void merge(Node*& t, Node* l, Node* r) {
    if (!l || !r) { t = l ? l : r; return; }
    push(l); push(r);
    if (l->pri > r->pri) {
        // l is root; its right child merges with r.
        merge(l->r, l->r, r);
        t = l;
    } else {
        // r is root; its left child merges with l.
        merge(r->l, l, r->l);
        t = r;
    }
    pull(t);
}

// --- High-level operations ---

void insert(Node*& t, int pos, int val) {
    // pos is 0-indexed insertion point.
    Node *l, *r;
    split(t, pos, l, r);
    Node* nd = new Node(val);
    merge(l, l, nd);
    merge(t, l, r);
}

void erase(Node*& t, int pos) {
    Node *l, *m, *r;
    split(t, pos, l, r);      // l = [0..pos-1]
    split(r, 1, m, r);        // m = [pos], r = [pos+1..]
    delete m;                  // free memory
    merge(t, l, r);
}

// Reverse subarray [l_pos, r_pos) (0-indexed, half-open).
void reverse(Node*& t, int l_pos, int r_pos) {
    Node *a, *b, *c;
    split(t, l_pos, a, b);
    split(b, r_pos - l_pos, b, c);
    if (b) b->rev ^= 1;       // lazy tag
    merge(b, b, c);
    merge(t, a, b);
}

// Range assign val to [l_pos, r_pos).
void range_assign(Node*& t, int l_pos, int r_pos, int val) {
    Node *a, *b, *c;
    split(t, l_pos, a, b);
    split(b, r_pos - l_pos, b, c);
    apply_assign(b, val);
    merge(b, b, c);
    merge(t, a, b);
}

// Query sum of [l_pos, r_pos).
long long query_sum(Node*& t, int l_pos, int r_pos) {
    Node *a, *b, *c;
    split(t, l_pos, a, b);
    split(b, r_pos - l_pos, b, c);
    long long res = gsum(b);
    merge(b, b, c);
    merge(t, a, b);
    return res;
}

// Build treap from array in O(n) expected time.
Node* build(const vector<int>& a, int lo, int hi) {
    if (lo >= hi) return nullptr;
    int mid = (lo + hi) / 2;
    Node* t = new Node(a[mid]);
    t->l = build(a, lo, mid);
    t->r = build(a, mid + 1, hi);
    pull(t);
    return t;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int& x : a) cin >> x;

    // Build from array (faster than n individual inserts).
    Node* root = build(a, 0, n);

    while (q--) {
        int type; cin >> type;
        if (type == 1) {           // insert val at pos
            int pos, val; cin >> pos >> val;
            insert(root, pos, val);
        } else if (type == 2) {    // erase at pos
            int pos; cin >> pos;
            erase(root, pos);
        } else if (type == 3) {    // reverse [l, r)
            int l, r; cin >> l >> r;
            reverse(root, l, r);
        } else if (type == 4) {    // assign val to [l, r)
            int l, r, val; cin >> l >> r >> val;
            range_assign(root, l, r, val);
        } else {                   // query sum [l, r)
            int l, r; cin >> l >> r;
            cout << query_sum(root, l, r) << "\n";
        }
    }
    return 0;
}

Pre-code Sanity Check

Before you start typing: are priorities actually random (mt19937, not pri = val)? Is your split splitting by key or by size (implicit index)—and have you accidentally mixed the two in the same tree? Does every split and merge call pull(node) to fix sizes and aggregates on the way out? If you are using lazy tags, do both split and merge start with push(node) on the way in? And are you using a node pool instead of new/delete to avoid allocator overhead?

The whole thing distills to one line: BST by key, heap by luck—split and merge do everything.

---

Operations Reference

All complexities are expected (randomized), where $n$ is the number of elements.

Operation	Time	Space	Notes
split(t, k)	$O(\log n)$	$O(\log n)$ stack	Splits into first $k$ and rest
merge(l, r)	$O(\log n)$	$O(\log n)$ stack	All keys in l < all keys in r
insert(pos, val)	$O(\log n)$	$O(1)$ new node	= split + merge + merge
erase(pos)	$O(\log n)$	$O(1)$ freed	= split + split + merge
reverse(l, r)	$O(\log n)$	$O(1)$ lazy tag	Lazy propagation
range_assign(l, r, v)	$O(\log n)$	$O(1)$ lazy tag	Lazy propagation
query_sum(l, r)	$O(\log n)$	$O(1)$	Split-query-merge
build(array)	$O(n)$	$O(n)$	Recursive build from sorted data
Space per node	--	$O(1)$	~40-56 bytes typical
Total space	--	$O(n)$	One node per element

Problem Patterns

Implicit Array with O(log n) Insert/Delete

When: The problem says "insert element at position $i$" or "delete element at position $i$" among other operations. Arrays and vectors are $O(n)$ for this.

Approach: Implicit treap. insert(root, pos, val) and erase(root, pos).

// Insert val at 0-indexed position pos
void insert(Node*& t, int pos, int val) {
    Node *l, *r;
    split(t, pos, l, r);
    merge(l, l, new Node(val));
    merge(t, l, r);
}

Problems:

• CF 863D - Yet Another Array Queries Problem (1900)
• CF 197E - Opening Portals

Subarray Reversal

When: "Reverse subarray $[l,r]$" mixed with queries. Classic example: sort a permutation with minimum-cost reversals.

Approach: Lazy reversal tag. Split out [l, r], flip the rev bit, merge back.

void reverse(Node*& t, int l, int r) {
    Node *a, *b, *c;
    split(t, l, a, b);
    split(b, r - l + 1, b, c);  // note: +1 for closed interval
    b->rev ^= 1;
    merge(b, b, c);
    merge(t, a, b);
}

Problems:

• CF 785E - Anton and Permutation (2300)
• SPOJ REVREV - Reverse and Reverse

Cut and Paste (Cyclic Shift of Subarray)

When: "Move subarray $[l,r]$ to position $p$" or "cyclically shift subarray".

Approach: Three splits, rearrange, three merges.

// Move [l, r) to position p (after removing it from original position).
void cut_paste(Node*& t, int l, int r, int p) {
    Node *a, *b, *c;
    split(t, l, a, b);
    split(b, r - l, b, c);     // b = [l, r)
    merge(a, a, c);            // remove [l, r) from sequence
    Node *x, *y;
    // Adjust p since elements shifted after removal
    if (p > l) p -= (r - l);
    split(a, p, x, y);
    merge(x, x, b);
    merge(t, x, y);
}

Problems:

• CF 197E - Opening Portals
• CF 762F - Tree nesting

k-th Element / Order Statistics

When: Maintain a dynamic set supporting "find k-th smallest" and "insert/delete".

Approach: Explicit treap (BST by value). Split by value to find rank; use subtree sizes for k-th.

// Find k-th element (1-indexed) via implicit key.
int kth(Node* t, int k) {
    push(t);
    int left_size = cnt(t->l);
    if (k <= left_size) return kth(t->l, k);
    if (k == left_size + 1) return t->val;
    return kth(t->r, k - left_size - 1);
}

Problems:

• CF 1354D - Multiset (1900)
• CSES - List Removals

Persistent Treap

When: "Answer queries on historical versions" or "undo operations." Copy-on-write: instead of modifying nodes, create new copies during split/merge.

Approach: Each split/merge copies $O(\log n)$ nodes. Keep an array of roots, one per version.

Node* copy(Node* t) {
    if (!t) return nullptr;
    return new Node(*t);  // shallow copy
}

void split_persistent(Node* t, int k, Node*& l, Node*& r) {
    if (!t) { l = r = nullptr; return; }
    t = copy(t);  // copy before modify
    push(t);
    if (cnt(t->l) < k) {
        split_persistent(t->r, k - cnt(t->l) - 1, t->r, r);
        l = t;
    } else {
        split_persistent(t->l, k, l, t->l);
        r = t;
    }
    pull(t);
}

Problems:

• CF 707D - Persistent Bookcase (2200)
• CF 786C - Till I Collapse

Range Aggregate + Point Update on Dynamic Sequence

When: Segment-tree-style queries but with insertions/deletions that change the array length.

Approach: Store an aggregate (sum, min, max, gcd) in each node. pull() recalculates from children. Query via split-query-merge.

Problems:

• CF 863D - Yet Another Array Queries Problem (1900)
• CSES - Cut and Paste

The RMQ ↔ LCA Connection (Why Cartesian Trees Matter Beyond Treaps)

The Cartesian tree reveals a deep equivalence: range minimum queries on an array become lowest common ancestor queries on its Cartesian tree.

Setup: Given array A[0..n-1], build the Cartesian tree with BST on indices and min-heap on values.

Key fact: range_min(l, r) = A[LCA(l, r)]

  Array A: [5, 2, 8, 1, 6, 3, 7]
  Index:    0  1  2  3  4  5  6

  Cartesian tree (same as the Walkthrough above):

                  (idx=3, val=1)
                 /              \
         (idx=1, val=2)    (idx=5, val=3)
         /          \       /          \
   (idx=0,val=5)(idx=2,val=8)(idx=4,val=6)(idx=6,val=7)

  ┌───────────────────┬───────────────────────────────────┬────────┐
  │ Query             │ LCA path                          │ Answer │
  ├───────────────────┼───────────────────────────────────┼────────┤
  │ range_min(0, 2)   │ LCA(idx 0, idx 2) = idx 1        │ A[1]=2 │
  │ range_min(4, 6)   │ LCA(idx 4, idx 6) = idx 5        │ A[5]=3 │
  │ range_min(0, 6)   │ LCA(idx 0, idx 6) = idx 3 (root) │ A[3]=1 │
  │ range_min(2, 5)   │ LCA(idx 2, idx 5) = idx 3        │ A[3]=1 │
  └───────────────────┴───────────────────────────────────┴────────┘

Why it works: The root holds the global minimum and divides the array into left and right halves (BST property). For any range [l, r], the LCA of positions l and r is exactly the position of the minimum in that range— because the minimum must be an ancestor of both endpoints (heap property) and the lowest such ancestor (the BST property splits left/right precisely at each node's index).

When to use: Problems combining range-min with tree-ancestor reasoning, or where reducing RMQ to LCA (or vice versa) unlocks an efficient approach. Also foundational for understanding the $⟨O(n),O(1)⟩$ RMQ algorithm.

---

Contest Cheat Sheet

+--------------------------------------------------------------+
|                  IMPLICIT TREAP CHEAT SHEET                  |
+--------------------------------------------------------------+
| WHEN TO USE:                                                  |
|   - Insert/delete at arbitrary position O(log n)              |
|   - Reverse subarray                                          |
|   - Cut-and-paste subarray                                    |
|   - Anything a seg tree does + structural mutations           |
|                                                               |
| CORE PRIMITIVES:                                              |
|   split(t, k, l, r)  -- first k elements -> l, rest -> r     |
|   merge(t, l, r)      -- all keys in l < all keys in r       |
|                                                               |
| OPERATION RECIPES:                                            |
|   insert(pos, val)  = split(pos) + merge(l, node) + merge    |
|   erase(pos)        = split(pos) + split(1) + delete + merge |
|   reverse(l, r)     = split(l) + split(r-l) + tag + merge x2 |
|   query(l, r)       = split(l) + split(r-l) + read + merge   |
|                                                               |
| COMPLEXITIES:  All O(log n) expected                          |
|                                                               |
| MUST REMEMBER:                                                |
|   1. push() before accessing children in split/merge          |
|   2. pull() after modifying children in split/merge           |
|   3. mt19937 rng -- never use rand()                          |
|   4. Interval convention: be consistent (half-open vs closed) |
+--------------------------------------------------------------+

---

Gotchas & Debugging

Random Seed

• Never use rand()—it has terrible randomness, a small range (often 15-bit), and is slow. Use mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()). The rng() call in the Node constructor auto-assigns a good priority.
• A fixed seed (e.g., mt19937 rng(42)) is fine for local debugging but can be hacked on CF. Use a time-based seed in submissions.

Push-Down Discipline

• Always push() before accessing t->l or t->r in split() and merge(). Forgetting this is the #1 treap bug. Symptoms: wrong answers that depend on operation order and disappear when you remove reverse() calls.
• When you add a new lazy tag, update push(), pull(), and the apply function. Miss any one and you get silent corruption.

Push/Pull Order with Multiple Lazy Tags

• If you have both rev and assign: push assign before rev—just be consistent and think through whether assign invalidates a pending reversal.
• Rule of thumb: if tag A resets the state, apply it before tag B, which permutes it. Assignment resets; reversal permutes—so push assignment first.

Memory Management

• Each node is ~40–56 bytes. For $n={10}^5$ that is ~5 MB; fine. For $n={10}^6$ it is ~50 MB—still fine, but watch the memory limit.
• new Node(...) in a tight loop is slow due to allocator overhead. Use a node pool instead:

const int MAXN = 300005;
Node pool[MAXN];
int pool_idx = 0;
Node* new_node(int v) {
    pool[pool_idx] = Node(v);
    return &pool[pool_idx++];
}

With persistence, each operation copies $O(\log n)$ nodes. For $q={10}^5$ queries that is roughly ${10}^5\times 17\approx 2\times {10}^6$ nodes—size your pool accordingly.

Off-by-One in Implicit Keys

• Pick 0-indexed half-open intervals [l, r) and stick with it everywhere. Mixing conventions is the #2 source of bugs.
• split(t, k) gives the first k elements, so split(t, l) + split(remainder, r - l) extracts [l, r).

Recursion Depth

• Expected depth is $O(\log n)\approx 17$ for $n={10}^5$. Stack overflow is not a concern unless $n>{10}^6$ on a system with a small default stack. On CF the stack is usually 256 MB, so this is rarely an issue.

Debugging Tips

• Write a to_vector(Node* t) function that does an in-order traversal and returns the array. Print it after every operation during testing.
• Verify cnt values: after every pull(), assert cnt(t) == 1 + cnt(t->l) + cnt(t->r).
• Test with small cases ($n\le 10$) and compare against brute force.

vector<int> to_vec(Node* t) {
    if (!t) return {};
    push(t);
    auto l = to_vec(t->l);
    l.push_back(t->val);
    auto r = to_vec(t->r);
    l.insert(l.end(), r.begin(), r.end());
    return l;
}

Mental Traps

Trap 1: "Range minimum = root value."

Yes, the root of the Cartesian tree holds the global minimum—but that is the trivial case. The real power is that range_min(l, r) = value at LCA(l, r). The tree encodes all subarray minima simultaneously through ancestor relationships, not just the global one.

  Array: [5, 2, 8, 1, 6, 3, 7]

              (1)              <- "range_min = root" only gets you this
             /   \
           (2)   (3)           <- the tree structure gives you ALL subarray
          / \    / \              minima via LCA -- that's the real power
        (5)(8)(6) (7)

  range_min(0,2) = val at LCA(idx 0, idx 2) = val at idx 1 = 2
  range_min(4,6) = val at LCA(idx 4, idx 6) = val at idx 5 = 3

Trap 2: Confusing the Cartesian tree with a treap.

A Cartesian tree is the unique combinatorial object for a sequence: BST on positions, heap on values. No randomness—the structure is fully determined by the input. A treap assigns random priorities to achieve expected $O(\log n)$ height for a balanced BST. They share the dual BST+heap property, but the purpose is entirely different.

  Same 4 keys: A, B, C, D

  CARTESIAN TREE (values determine structure -- unique)
  values: [3, 1, 4, 2]

         B(1)              Determined by the data.
        /    \             Exactly one valid tree.
      A(3)   D(2)         Used for: RMQ, LCA, structure.
              /
           C(4)

  TREAP (random priorities -- varies each run)
  keys: A < B < C < D,  random pri: A->7, B->3, C->9, D->5

  Run 1:       B(3)       Run 2 (new random priorities):
              /    \
           A(7)   D(5)          C(1)
                  /            /    \
               C(9)         B(4)   D(6)
                            /
                          A(8)

  Different random seeds -> different tree shapes.
  Purpose: balanced BST with split/merge.

Trap 3: Thinking the $O(n)$ stack build is optional.

A naive build (insert each element into a BST while maintaining heap order) takes $O(n^2)$ worst case. The monotone-stack construction is $O(n)$ because each element is pushed and popped at most once. For $n$ up to ${10}^6$, this is the difference between AC and TLE. Know the stack trick.

Spot the Bug

Bug 1—Forgot to update size after merge:

void merge(Node*& t, Node* l, Node* r) {
    if (!l || !r) { t = l ? l : r; return; }
    if (l->pri > r->pri) { merge(l->right, l->right, r); t = l; }
    else { merge(r->left, l, r->left); t = r; }
    // missing: update(t);
}

Fix

t->size and any aggregates are stale. Every merge must end with update(t).

Bug 2—Missing push in split:

void split(Node* t, int k, Node*& l, Node*& r) {
    if (!t) { l = r = nullptr; return; }
    // push(t);  <- missing!
    int cur_key = get_size(t->left) + 1;
    // ...
}

Fix

With a pending reverse flag, t->left and t->right are conceptually swapped. get_size(t->left) reads the wrong child. Add push(t); first.

Bug 3—Deterministic priorities:

Node(int v) : val(v), pri(v), ... {}  // priority = value!

Fix

Correlated priorities degenerate the tree to $O(n)$ depth on sorted input. Use pri(rng()) with mt19937.

---

Can You...

Before moving on: given a sequence of distinct values, build the Cartesian tree by hand using the rightmost-path stack in $O(n)$. Explain why the Cartesian tree is unique for distinct values. State the dual property (BST on ___ + heap on ___) and why both parts matter. Given a Cartesian tree, compute range_min(l, r) as the LCA of positions l and r. Articulate when a Cartesian tree is the right choice for RMQ versus when a sparse table wins. Distinguish a Cartesian tree (deterministic, structure forced by the data) from a treap (randomized, used as a balanced BST). Explain why the stack-based build is $O(n)$, not $O(n\log n)$ or $O(n^2)$—the amortized argument is that each element is pushed and popped at most once.

---

Practice Problems

#	Problem	Source	Difficulty	Key Idea
1	Cut and Paste	CSES	Easy-Med	Basic split/merge on sequence
2	List Removals	CSES	Easy-Med	k-th element + delete
3	Multiset	CF 1354D	1900	Dynamic order statistics
4	Yet Another Array Queries	CF 863D	1900	Reverse + cyclic shift on array
5	Array	CF 86D	2400	Sqrt decomposition or treap
6	Splay	SPOJ	Hard	Splay / treap with lazy propagation
7	Persistent Bookcase	CF 707D	2200	Persistent structure, undo
8	Anton and Permutation	CF 785E	2300	Count inversions with swaps
9	Letters Removing	CF 899F	2300	BIT/treap for dynamic positions
10	Bicycle Race	CF 1776L	2500	Advanced treap application

---

Further Reading

• cp-algorithms: Treap (Cartesian Tree)—definitive reference with explicit and implicit variants.
• CF Blog: Implicit Treap by Roms—one of the earliest and most referenced tutorials on CF.
• CF Blog: Non-rotating Treap—modern split/merge approach.
• Algorithmica: Treap—performance-oriented discussion.
• E-Maxx (Russian)—classic reference.
• Cross-references: Segment Tree, Priority Queue and Heaps, Binary Indexed Tree (Fenwick).

---

Next Up: Persistent DSU—when you need to undo structural changes to a union-find.