Range Query on Version

Range queries work the same as regular segment trees:

function query(node, nodeL, nodeR, l, r)
    if node is null or r < nodeL or nodeR < l then
        return 0  // identity for sum

    if l <= nodeL and nodeR <= r then
        return node.sum

    mid := (nodeL + nodeR) / 2
    leftSum := query(node.left, nodeL, mid, l, r)
    rightSum := query(node.right, mid + 1, nodeR, l, r)
    return leftSum + rightSum

The only difference: you start from a specific version's root.

result := query(roots[version], 0, n - 1, l, r)

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