Point Update

To update index $i$ to value $v$:

• Find the leaf for index $i$
• Update the leaf
• Propagate changes up to the root

def update(node, start, end, idx, val):
    if start == end:
        tree[node] = val
    else:
        mid = (start + end) // 2
        if idx <= mid:
            update(2*node, start, mid, idx, val)
        else:
            update(2*node+1, mid+1, end, idx, val)
        tree[node] = tree[2*node] + tree[2*node+1]

Time: $O(\log n)$. You traverse one path from root to leaf (height $\log n$), updating nodes along the way.

After updating a leaf, every ancestor on the path to root must be recomputed.