Version Queries Solution

class VersionedArray:
    roots: list of segment tree roots
    n: int

    function __init__(arr)
        roots := [build(arr, 0, n - 1)]

    function update(index, value)
        newRoot := persistentUpdate(roots.last(), 0, n - 1, index, value)
        roots.append(newRoot)

    function query(version, l, r)
        return rangeSum(roots[version], 0, n - 1, l, r)

Each update appends a new root. Queries access the appropriate version's root.

Time: $O(\log n)$ per operation.

Space: $O(n + m \log n)$ for $n$ initial elements and $m$ updates.