Persistent radix vectors: copy one indexed path per revision

Last updated: 5 Oct 20269 min read

tutorial

A persistent radix vector routes an integer position through a shallow, fixed-branching tree. Replacing one value copies only nodes on that index path and shares every untouched child with the previous root. Appending follows the next position; when the root's current capacity is full, a new root raises the height and keeps the old root as its first child. Each returned vector carries its own root, height, and length. The program uses four-way tuples and no mutable tail buffer so the sharing rule stays visible. An old revision remains readable after later replacements and appends, provided callers treat stored payload objects as immutable values.

Operational case

The morning case vector is 19, 47, 83, 149, 173. A correction produces a new revision with 103 at position two, and an evening append adds 211. The morning revision still reports 83 at position two. Five elements cross the four-slot root capacity, so this trace exercises the height increase rather than only a single leaf. A shallow root copy would fail if its child tuples were edited in place; this version allocates new tuples all the way to the changed leaf. It does not implement arbitrary middle insertion, which would renumber later positions.

Working Python program

BRANCH = 4


def replace_path(node, height, index, value):
    children = list(node)
    slot = (index // (BRANCH ** height)) % BRANCH
    while len(children) <= slot:
        children.append(None)
    if height == 0:
        children[slot] = value
    else:
        children[slot] = replace_path(children[slot] or (), height - 1, index, value)
    return tuple(children)


class CaseVector:
    def __init__(self, root=(), height=0, length=0):
        self.root, self.height, self.length = root, height, length

    def at(self, index):
        if not 0 <= index < self.length:
            raise IndexError(index)
        node = self.root
        for height in range(self.height, -1, -1):
            node = node[(index // (BRANCH ** height)) % BRANCH]
        return node

    def replace(self, index, value):
        if not 0 <= index < self.length:
            raise IndexError(index)
        return CaseVector(replace_path(self.root, self.height, index, value), self.height, self.length)

    def append(self, value):
        root, height = self.root, self.height
        if self.length == BRANCH ** (height + 1):
            root, height = (root,), height + 1
        return CaseVector(replace_path(root, height, self.length, value), height, self.length + 1)

    def values(self):
        return [self.at(index) for index in range(self.length)]


if __name__ == "__main__":
    morning = CaseVector()
    for case_id in [19, 47, 83, 149, 173]:
        morning = morning.append(case_id)
    corrected = morning.replace(2, 103)
    evening = corrected.append(211)
    print(morning.values())
    print(corrected.values())
    print(evening.values())

Output

[19, 47, 83, 149, 173]
[19, 47, 103, 149, 173]
[19, 47, 103, 149, 173, 211]

Time, space, and tradeoff

At branching factor B and length N, indexed read visits O(log_B N) nodes. Replace and append copy O(B log_B N) tuple slots in this direct Python implementation and retain O(log_B N) new nodes per revision; the root-height increase is constant additional work. Listing all values takes O(N log_B N) here because it repeatedly calls indexed read. Historical roots keep shared subtrees alive, so retaining many revisions costs memory. A mutable resizable array has simpler constants when revisions are unnecessary; a persistent ordered map serves keyed lookup rather than contiguous positions.

Common Mistakes

Do not mutate a shared child tuple or mutable payload and call the revision immutable.
Do not forget the root height increase when length reaches its current capacity.
Do not claim constant-time middle insertion for an indexed radix vector.
Do not compare revision memory to one flat array while retaining every old root.

Connected lessons

Compare its input and update contract with X-fast trie: predecessor and successor in a fixed integer universe, Compressed suffix trees: locate patterns across a frozen text, Disjoint interval unions: maintain covered maintenance time, then complete the structure audit and decision quiz.

data structures

range-query-structures