Query and Update Functions

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.