Persistent Treap, in depth: path-copying split and merge, the shared-priority trap, size-weighted merges and versioned sequences

Path copying in a treap

The ephemeral treap mutates child pointers during split and merge. The persistent one builds a fresh node wherever the ephemeral one would have assigned a pointer, and otherwise reuses the old subtree unchanged. Sizes and aggregates (here, a sum) are computed in the constructor, so a node is complete and immutable from the moment it exists.

import random

class Node:
    __slots__ = ("val", "left", "right", "size", "total")
    def __init__(self, val, left=None, right=None):       # nodes are immutable after this
        self.val, self.left, self.right = val, left, right
        self.size = 1 + size(left) + size(right)
        self.total = val + total(left) + total(right)

def size(t):  return t.size if t else 0
def total(t): return t.total if t else 0

def split(t, k):
    """(first k elements, the rest). Copies only the nodes on one root-to-leaf path."""
    if not t:
        return None, None
    if size(t.left) >= k:
        l, r = split(t.left, k)
        return l, Node(t.val, r, t.right)
    l, r = split(t.right, k - size(t.left) - 1)
    return Node(t.val, t.left, l), r

def merge(a, b, rng):
    """Concatenate. Root chosen with probability size(a) / (size(a) + size(b))."""
    if not a: return b
    if not b: return a
    if rng.randrange(a.size + b.size) < a.size:
        return Node(a.val, a.left, merge(a.right, b, rng))
    return Node(b.val, merge(a, b.left, rng), b.right)

def insert(t, i, val, rng):
    l, r = split(t, i)
    return merge(merge(l, Node(val), rng), r, rng)

def erase(t, i, rng):
    l, r = split(t, i)
    _, r = split(r, 1)
    return merge(l, r, rng)

def range_sum(t, i, j):                      # sum of positions [i, j), no new version kept
    _, r = split(t, i)
    m, _ = split(r, j - i)
    return total(m)

Note what is missing: there is no priority field. The merge flips a coin weighted by subtree sizes instead. The next section explains why that is not just a space-saving trick but a correctness requirement for implicit persistent treaps.

Queries such as range_sum also split, which allocates nodes, but the results are discarded and garbage collected. If allocation on reads matters, write a read-only descent that walks the tree with position arithmetic and allocates nothing.

The shared-priority trap

An ordinary treap stores a random priority in each node and keeps heap order on priorities. Its expected O(log n) depth rests on one assumption: the priorities of the nodes in a tree are independent and distinct. Persistence can break that assumption. Once versions share nodes, you can merge a version with a slice of itself, as in copy and paste or doubling a sequence, and the same node, with the same priority, appears in both operands. At the top of a self-merge the two roots are the same node. The comparison ties, and the next level ties again. The heap property forces the copies into a long chain.

Measured: start from two elements and repeatedly replace t with merge(t, t). With stored priorities, the depth after k doublings was exactly n/2 + 1: 4,097 for 8,192 elements after 12 doublings, and Python's recursion limit was exceeded soon after. With the size-weighted merge from the code above, depth after 12 doublings was 29. After 20 doublings, 2,097,152 elements, it was 48, and the 20 doublings together allocated only 281 new nodes, because each doubling copies only a couple of paths.

Why the weighted coin works: in a treap built from independent random priorities, the root of merge(a, b) is the highest-priority node among all of them, and that node lies in a with probability size(a) / (size(a) + size(b)). Flipping that coin at each step reproduces this rule without storing priorities. When a and b are independent random treaps, the result is distributed exactly as a random treap. When they share nodes, as in a self-merge, the operands are correlated and that exact guarantee no longer holds. But the coin never lets a node tie with itself, each step still picks the root in the right proportion, and the measured depth stays logarithmic. The cost is one random number per merge step.

Keyed treaps used as versioned sets are different. Keys are unique within one tree, so a node cannot meet itself, and priorities derived by hashing the key are safe and even give a canonical shape. The treap in depth covers that trick and join-based set operations, which carry over to persistence unchanged once every pointer assignment becomes a node copy.

Worked example: versions, undo and cost

Build v0 = [5, 3, 8, 1] by four inserts. Then v1 = insert(v0, 2, 7) gives [5, 3, 7, 8, 1] with sum 24, and v2 = erase(v1, 0) gives [3, 7, 8, 1] with sum 19. Afterwards, v0 still reads [5, 3, 8, 1] with sum 17. Each version is just a root pointer, so an undo stack is a list of roots, and "undo" means popping it. Redo, branching histories and diffing two versions by walking shared subtrees all come free.

Cost at scale: building a 100,000-element sequence by inserts at random positions allocated 4,897,307 nodes, about 49 per insert, and finished with depth 43. A further 1,000 inserts at that size allocated about 54 nodes each. Each insert does one split and two merges, and each copies a path of expected length around 2 ln n. The constant is real: persistence costs tens of nodes per update, and retaining every version of a busy structure costs memory linear in the number of updates.

Copy and paste is where the structure shines. To copy positions [i, j) of version v and paste them at position k, split v twice to get the slice s. Then split v at k and return merge(merge(left, s), right). That is three splits and two merges: O(log n) expected time and O(log n) new nodes, whether the slice holds ten elements or ten million. The slice's nodes are not copied at all; the new version simply points at them, and the old version still points at them too. An array-backed buffer would copy j - i elements, and an ephemeral treap would have to clone the slice to avoid aliasing it. This is also exactly the operation that makes a node meet itself: paste a slice next to its own source, and both operands of the merge contain the same nodes. That is why the size-weighted coin is not optional for an editor buffer. The doubling experiment above is the extreme case of repeated self-pastes, and it stayed at depth 48.

Lazy tags under persistence

Range updates (add to a range, reverse a range) use lazy tags. In an ephemeral treap you push a tag down by mutating the children. In a persistent one, the children may be shared with other versions, so pushing down must copy them: construct new children with the tag applied, then a new parent pointing at them. Two rules keep this sound. Tags must compose (two pending adds become one add; two reverses cancel), and a node's aggregate must already include its own pending tag, so reading a node never requires pushing first. Pushes then happen only along paths that split or merge already copy, and the asymptotic cost is unchanged. The constant roughly doubles, because each visited node may now copy both children.

The same pattern applies to persistent segment trees with lazy propagation. The treap's advantage is that it also supports insertion, deletion and concatenation, which a fixed-shape segment tree cannot.

Memory, retention and concurrency

In a garbage-collected language, versions you drop are reclaimed automatically, and shared subtrees survive as long as any live version references them. In C++ or Rust, use reference counting (std::shared_ptr or Rc/Arc) or an arena with periodic compaction. Reference counting turns every node copy into increments, and freeing one deep version can cascade, so arenas usually win when versions are dropped in bulk.

Long histories need a retention policy: keep the last N versions, or checkpoints plus recent ones. When the node count passes a threshold, rebuild: flatten the live version in order and build a fresh balanced tree in O(n). Rebuilding also resets shapes left lopsided by unlucky coins.

Concurrency is where immutability pays off. A version cannot change, so any number of threads can read it without locks. A writer builds the next version privately and publishes it with one atomic reference swap, and readers keep whichever root they grabbed, which gives snapshot isolation for free. With several writers, use compare-and-swap on the root and retry on conflict. Writers then race, but readers never wait. The same versioning idea underlies persistent union-find.

Failure modes

Trade-offs

Versus an ephemeral treap with an undo log, the persistent treap gives O(1) access to any version and lock-free readers. The price is several times the allocation per update. Versus a persistent segment tree, it handles insertion and concatenation, but has randomized rather than worst-case depth and a larger constant. Versus wide persistent vectors (32-way tries), it supports arbitrary splits and joins, while the tries win on cache behaviour for append-heavy and index-heavy workloads. Pick the treap when you need split, concatenate and old versions together, which is the rope-with-history case.

What to do next

1. Implement the immutable node, split and merge above, and test that every old root still produces its original contents after 10,000 random operations.
2. Use the size-weighted merge coin for implicit treaps; add a test that self-merges 20 times and asserts the depth stays under a small multiple of log2 n.
3. Add an aggregate and a lazy tag that composes, and check range results against a plain list on random workloads.
4. Measure nodes allocated per update in your language and set a retention and rebuild policy from that number.
5. If multiple threads read, publish versions through an atomic reference and remove the locks from the read path.