To update index to value :
- Find the leaf for index
- 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: . You traverse one path from root to leaf (height ), updating nodes along the way.
After updating a leaf, every ancestor on the path to root must be recomputed.