Persistent Segment Tree

A persistent segment tree supports:

• query(version, l, r): Range query on version
• update(version, index, value): Create new version with point update

The structure is the same as persistent array, but internal nodes store aggregates (sum, min, max).

class PersistentSegTree:
    class Node:
        sum: int
        left, right: Node

    function update(node, l, r, index, value)
        newNode := new Node()
        if l = r then
            newNode.sum := value
            return newNode

        mid := (l + r) / 2
        if index <= mid then
            newNode.left := update(node.left, l, mid, index, value)
            newNode.right := node.right
        else
            newNode.left := node.left
            newNode.right := update(node.right, mid + 1, r, index, value)

        newNode.sum := newNode.left.sum + newNode.right.sum
        return newNode