Randomized Treaps & Implicit Treaps: Rebalancing Without Rotations via split and merge

The split and merge Paradigm & Implicit Treaps (Dynamic Rope Arrays)

Instead of bottom-up rotations, every Treap operation reduces to two recursive primitives that run in $O(\log N)$ expected time:

• split(T, key) -> (L, R): Partitions Treap $T$ into two valid Treaps: $L$ (all nodes with key $\le \text{key}$) and $R$ (all nodes with key $> \text{key}$). If $T.\text{key} \le \text{key}$, then $T$ and all of $T.\text{left}$ belong to $L$; we recursively split $T.\text{right}$ into $(T.\text{right}, R)$ and return $(T, R)$. Symmetric when $T.\text{key} > \text{key}$.
• merge(L, R) -> T: Combines two Treaps $L$ and $R$ under the precondition that every key in $L$ is strictly $\le$ every key in $R$ ($max(L) \le \min(R)$). Whichever root has the higher random priority ($L.\text{prio} > R.\text{prio}$) becomes the combined root, and we recursively merge its right child with $R$ (or $L$ with $R.\text{left}$).

With split and merge, every dictionary and sequence operation is a 2-line composition:

• insert(T, newNode): (L, R) = split(T, newNode.key); return merge(merge(L, newNode), R);
• erase(T, key): (L, M) = split(T, key - 1); (Target, R) = split(M, key); return merge(L, R);
• Implicit Treap (Index-Keyed Sequence / Rope): Drop explicit keys altogether! Maintain only subtree sizes $\text{sz}(u) = 1 + \text{sz}(u.\text{left}) + \text{sz}(u.\text{right})$. Now a node's 0-based array index in the current subtree is simply $\text{sz}(u.\text{left})$! Calling splitBySize(T, k) cuts an array of length $N$ at position $k$ in $O(\log N)$ time, enabling $O(\log N)$ arbitrary range cut-and-paste, range reversal (via a lazy bool rev bit that swaps children), and range sum/min queries!

Implementation: Implicit Treap with $O(\log N)$ Range Reversal (split + merge)

// C++20: Implicit Treap supporting O(log N) Subarray Reversal [l, r] via split & merge
#include <cstdint>
#include <utility>

struct ImplicitTreapNode {
    int val;
    uint64_t prio;
    int sz = 1;
    bool rev = false; // Lazy range-reversal tag
    ImplicitTreapNode *l = nullptr, *r = nullptr;

    ImplicitTreapNode(int v, uint64_t p) : val(v), prio(p) {}
};

inline int size(const ImplicitTreapNode* t) noexcept { return t ? t->sz : 0; }

inline void pull(ImplicitTreapNode* t) noexcept {
    if (t) t->sz = 1 + size(t->l) + size(t->r);
}

inline void pushLazy(ImplicitTreapNode* t) noexcept {
    if (t && t->rev) {
        std::swap(t->l, t->r);
        if (t->l) t->l->rev ^= true;
        if (t->r) t->r->rev ^= true;
        t->rev = false;
    }
}

// Splits T into L (first k elements) and R (remaining N - k elements)
std::pair<ImplicitTreapNode*, ImplicitTreapNode*> splitBySize(ImplicitTreapNode* t, int k) {
    if (!t) return {nullptr, nullptr};
    pushLazy(t);
    int leftCount = size(t->l);
    if (k <= leftCount) {
        auto [L, R] = splitBySize(t->l, k);
        t->l = R;
        pull(t);
        return {L, t};
    } else {
        auto [L, R] = splitBySize(t->r, k - leftCount - 1);
        t->r = L;
        pull(t);
        return {t, R};
    }
}

ImplicitTreapNode* merge(ImplicitTreapNode* L, ImplicitTreapNode* R) {
    if (!L || !R) return L ? L : R;
    pushLazy(L);
    pushLazy(R);
    if (L->prio > R->prio) {
        L->r = merge(L->r, R);
        pull(L);
        return L;
    } else {
        R->l = merge(L, R->l);
        pull(R);
        return R;
    }
}

// Reverses contiguous subarray [l, r] (0-indexed inclusive) in O(log N) expected time
ImplicitTreapNode* reverseRange(ImplicitTreapNode* root, int l, int r) {
    auto [t1, t23] = splitBySize(root, l);
    auto [t2, t3]  = splitBySize(t23, r - l + 1);
    if (t2) t2->rev ^= true;
    return merge(t1, merge(t2, t3));
}