A persistent segment tree supports:
query(version, l, r): Range query on versionupdate(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