Range Minimum Query
The minimum of a range, answered from O(log n) nodes of a min tree.
Decision · step 2 of 13Segment Tree: Minimum of indices 1 to 6
Node 1 covers indices 0 to 7, holding 1. That straddles the edge, so split into both children.
What you will see
The same query answered by brute force, sparse table and segment tree; contributing cells light up.
Cost
| Best | O(1) |
|---|---|
| Average | O(log n) |
| Worst | O(n) |
| Space | O(n) |
Depends on the structure; O(1) sparse tableO(log n) segment treeO(n) naive.
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.