Segment Tree Query and Update
A query takes whole nodes inside the range and splits only the ones on its edge.
Decision · step 2 of 9Segment Tree: Sum of indices 2 to 5
Node 1 covers indices 0 to 7, holding 36. That straddles the edge, so split into both children.
What you will see
Nodes whose ranges are fully inside light up and stop; partial ones recurse.
Cost
| Best | O(log n) |
|---|---|
| Average | O(log n) |
| Worst | O(log n) |
| Space | O(n) |
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input, try operations in any order.
Screen readers: Structure nodes announce the range they cover and their value; each step announces which nodes answer the query.
Reduced motion: Contributing nodes highlight statically; no path animation.
Before this
Related
Taught by the same lesson
Segment Tree covers these too, in the same run.