Range query: three cases at every node
Example:
query(1, 3) on 4 elements
query(2, 6) on 8 elements
← Prev
Next →
▶ Play
Reset
Input array (query range highlighted)
Contributions collected so far
never visited
visiting now
partial overlap → recurse
inside → use cached sum
outside → contributes 0