Point update: one path down, recompute on the way up
Example:
update(2, 0) on 4 elements
update(5, 9) on 8 elements
Build [2, 1, 5, 3] from scratch
← Prev
Next →
▶ Play
Reset
Input array
arr
(0-indexed)
Flat tree array
tree
(1-indexed, heap layout: children of
cur
at
2·cur
and
2·cur+1
)
untouched
current node
on the path, sum stale
written / recomputed