function query(node, l, r, index)
if l = r then
return node.value
mid := (l + r) / 2
if index <= mid then
return query(node.left, l, mid, index)
else
return query(node.right, mid + 1, r, index)
function update(node, l, r, index, value)
if l = r then
newNode := new Node()
newNode.value := value
return newNode
mid := (l + r) / 2
newNode := new Node()
if index <= mid then
newNode.left := update(node.left, l, mid, index, value)
newNode.right := node.right // share unchanged subtree
else
newNode.left := node.left // share unchanged subtree
newNode.right := update(node.right, mid + 1, r, index, value)
return newNode
Note: unchanged child is shared, not copied.