Persistent Array Implementation

class PersistentArray:
    class Node:
        value: any // only for leaves
        left, right: Node

    roots: list of Node // roots[i] = root of version i
    n: int

    function build(arr, l, r)
        if l = r then
            return new leaf Node with value arr[l]
        mid := (l + r) / 2
        node := new Node()
        node.left := build(arr, l, mid)
        node.right := build(arr, mid + 1, r)
        return node

    function get(version, index)
        return query(roots[version], 0, n - 1, index)

    function set(version, index, value)
        newRoot := update(roots[version], 0, n - 1, index, value)
        roots.append(newRoot)
        return len(roots) - 1 // new version number