Segment Tree
A binary tree whose leaves are the array and whose every parent summarises its two children.
Result · step 8 of 9Segment Tree: Build a sum tree
Node 1 covers indices 0 to 7. Its children hold 16 and 20, so it holds 36.
What you will see
A query lights up O(log n) nodes that exactly tile the range; an update walks one root-to-leaf path.
Cost
| build | O(n) |
|---|---|
| query | O(log n) |
| update | 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: Each element is an accessibility element with position, value and state; structural changes are announced per step.
Reduced motion: Elements appear at their destination with a crossfade; no travel longer than the element's own size.
Before this
Taught by the same lesson
Segment Tree covers these too, in the same run.