Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Implicit treap: edit positions and reverse a range

Last updated: 5 Oct 20269 min read
tutorial
IntermediateBy AITrove Editorial

An implicit treap is a sequence tree whose in-order position comes from subtree sizes, not from comparing stored task IDs. Split separates the first K elements from the remainder. Merge joins two sequences whose relative order is already defined. Random priorities tend to keep the tree shallow, while each node's size makes positional splits possible. A reversal flag marks an entire subtree as logically reversed; push swaps its children and passes the flag down only when the subtree is next inspected. The shown API supports insertion at a position and reversal of a half-open range. It keeps duplicate task IDs as separate positions because task IDs are payloads, not search keys.

Operational case

Start with tasks T-19, T-47, T-61, and T-83. Reverse [1, 4) to get T-19, T-83, T-61, T-47. Insert T-26 at position 2 and the order becomes T-19, T-83, T-26, T-61, T-47. The snapshot walks all five tasks and forces pending reversals down before reading nodes. A split is destructive to the current root links until the pieces are merged back; callers should expose operations through one owner instead of handing mutable subtree roots to unrelated writers. The fixed random seed makes the demonstration repeatable, not adversary-resistant.

Working Python program

python
"""Position-indexed treap with lazy range reversal."""

from dataclasses import dataclass
from random import Random


@dataclass
class SequenceNode:
    task_id: str
    priority: float
    left: "SequenceNode | None" = None
    right: "SequenceNode | None" = None
    size: int = 1
    reverse_pending: bool = False


def length(node: SequenceNode | None) -> int:
    return node.size if node else 0


def push(node: SequenceNode | None) -> None:
    if node and node.reverse_pending:
        node.left, node.right = node.right, node.left
        for child in (node.left, node.right):
            if child:
                child.reverse_pending ^= True
        node.reverse_pending = False


def refresh(node: SequenceNode) -> None:
    node.size = 1 + length(node.left) + length(node.right)


def split(node: SequenceNode | None, count: int) -> tuple[SequenceNode | None, SequenceNode | None]:
    if node is None:
        return None, None
    push(node)
    if count <= length(node.left):
        first, node.left = split(node.left, count)
        refresh(node)
        return first, node
    node.right, second = split(node.right, count - length(node.left) - 1)
    refresh(node)
    return node, second


def merge(first: SequenceNode | None, second: SequenceNode | None) -> SequenceNode | None:
    if first is None or second is None:
        return first or second
    if first.priority > second.priority:
        push(first)
        first.right = merge(first.right, second)
        refresh(first)
        return first
    push(second)
    second.left = merge(first, second.left)
    refresh(second)
    return second


class DispatchSequence:
    def __init__(self, seed: int = 47):
        self.root: SequenceNode | None = None
        self.random = Random(seed)

    def insert(self, position: int, task_id: str) -> None:
        if not 0 <= position <= length(self.root):
            raise IndexError(position)
        first, second = split(self.root, position)
        self.root = merge(merge(first, SequenceNode(task_id, self.random.random())), second)

    def reverse(self, start: int, stop: int) -> None:
        if not 0 <= start <= stop <= length(self.root):
            raise IndexError((start, stop))
        first, remainder = split(self.root, start)
        middle, last = split(remainder, stop - start)
        if middle:
            middle.reverse_pending ^= True
        self.root = merge(merge(first, middle), last)

    def snapshot(self) -> list[str]:
        result = []

        def walk(node: SequenceNode | None) -> None:
            if node:
                push(node)
                walk(node.left)
                result.append(node.task_id)
                walk(node.right)

        walk(self.root)
        return result


dispatch = DispatchSequence()
for task_id in ["T-19", "T-47", "T-61", "T-83"]:
    dispatch.insert(length(dispatch.root), task_id)
dispatch.reverse(1, 4)
dispatch.insert(2, "T-26")
print(dispatch.snapshot())
print(length(dispatch.root))

Output

Output
['T-19', 'T-83', 'T-26', 'T-61', 'T-47']
5

Time, space, and tradeoff

With independent random priorities, expected height is O(log N). Insert and range reverse perform a constant number of splits or merges and take expected O(log N) time and O(log N) recursion space. A snapshot takes O(N) time and O(N) output space. The worst-case treap can have O(N) height, causing O(N) operations and recursion-depth failure in Python. The structure stores O(N) nodes with size, priority, and lazy-reversal state. A Python list is usually better for small sequences or bulk iteration; this tree pays pointer overhead to make repeated middle edits and interval reversals cheap in expectation.

Common Mistakes

  • Do not compare task IDs to choose a sequence position; use left-subtree size.
  • Do not split or walk below a pending reversal before pushing it.
  • Do not forget to refresh size after changing a child link.
  • Do not advertise worst-case logarithmic behavior for randomized priorities.

Connected lessons

Apply the invariant in the sparse readings and task constraints project, then check the operations quiz.

Piece tables: edit text through source spans adds a related operation contract.

Gap labels: compare dispatch order across middle inserts adds a related structure with a different operation boundary.

Ordered treaps: split, join, and select depot keys adds a related structure with a different operation boundary.

data structures
range-query-structures
Storage details