Range Minimum Query
The minimum of a range, answered from O(log n) nodes of a min tree.
Segment 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.
Cost
- Best
- O(1)
- Average
- O(log n)
- Worst
- O(n)
- Space
- O(n)
Depends on the structure. O(1) sparse table O(log n) segment tree O(n) naive.
Before this
Related
Leads to
Topics that need this one first.
Taught by the same lesson
Segment Tree covers these too, in the same run.