Implicit Treap Rope with O(log n) Split, Merge & Lazy Reverse

Cartesian Trees Over Implicit Array Indices

A Treap combines a Binary Search Tree (ordered by key) with a Binary Heap (ordered by random priority). When we replace explicit keys with implicit indices—computed on the fly from size(node.left)—the treap becomes a dynamic array (or Rope) where every sequence operation runs in $O(\log n)$ expected time.

The Split-Merge Paradigm

All sequence mutations reduce to two primitives:

1. split(t, k): Partitions treap t into [left, right] where left holds the first $k$ elements and right holds the remaining $n - k$ elements.
2. merge(left, right): Concatenates two treaps under the precondition that all elements in left precede all elements in right, choosing the root with the larger random priority.

Lazy Range Reversal & Cut-and-Paste

To reverse a subarray $[l, r]$ in $O(\log n)$ time:

1. Split into $T_1 = [0, l-1]$, $T_2 = [l, r]$, and $T_3 = [r+1, n-1]$.
2. Toggle the lazy reversal bit T2.rev = !T2.rev.
3. Merge merge(merge(T1, T2), T3).

Similarly, moving a block of text from $[l, r]$ to any new position requires two splits and two merges—the core operation of high-performance text editors and sequence engines.

Curriculum Connections

• Treaps & The Split-Merge Paradigm
• BST Augmentation & Order-Statistic Trees
• Lazy Propagation & Beats

Guided Implementation Walkthrough (4 Progressive Steps)

Step 1: Lazy Reversal Push & Subtree Pull

• Core Mechanical Concept: Lazy Reversal Push & Subtree Pull
• Target Module: index.js (Step1)
• Engineering Specification: Implement _push(t) to lazily swap t.left and t.right when t.rev is set and propagate the toggle to children. Implement _pull(t) to maintain t.size and t.sum.
• Verification Invariant: verifies Step 1: Lazy Reversal Push & Subtree Pull

Step 2: Implicit Split & Priority Merge

• Core Mechanical Concept: Implicit Split & Priority Merge
• Target Module: index.js (Step2)
• Engineering Specification: Implement split(t, k) using leftSize = _sz(t.left) as the implicit key, and merge(left, right) comparing left.priority >= right.priority to maintain the Cartesian heap invariant.
• Verification Invariant: verifies Step 2: Implicit Split & Priority Merge

Step 3: Arbitrary-Index Insert & Delete

• Core Mechanical Concept: Arbitrary-Index Insert & Delete
• Target Module: index.js (Step3)
• Engineering Specification: Implement insertAt(index, value) and deleteAt(index) in $O(\log n)$ time using split and merge.
• Verification Invariant: verifies Step 3: Arbitrary-Index Insert & Delete

Step 4: Range Reversal, Cut-and-Paste & Range Sum

• Core Mechanical Concept: Range Reversal, Cut-and-Paste & Range Sum
• Target Module: index.js (Step4)
• Engineering Specification: Split the treap into [0..l-1], [l..r], and [r+1..n-1], apply lazy reversal or read t2.sum on the middle treap, and merge the pieces back.
• Verification Invariant: verifies Step 4: Range Reversal, Cut-and-Paste & Range Sum

Asymptotic & Memory Layout Guarantees

• Category: Balanced Trees & Augmentation
• Difficulty: Advanced (~45 minutes)
• Key Architectural Highlights:
  • Implicit array indexing derived purely from dynamic left-subtree sizes
  • Deterministic xorshift32 priority generator maintaining expected O(log n) tree height
  • O(log n) substring cut-and-paste, range sum, and lazy range reversal via split and merge
• Tags & Primitives: Implicit Treap, Rope, Split-Merge Paradigm, Lazy Reversal, Randomized BST

Production Systems Context & Verification

This from-scratch implementation is engineered with zero external dependencies and deterministic verification harnesses. Every internal invariant—from pointer restoration and bitmask addressing to amortized potential bounds and tree height balance—is asserted directly in test.js. Use the interactive browser workbench above to complete the guided steps in Guided Lab mode or inspect and benchmark the complete reference architecture in Full Solution mode.