AlgoScope

Range Minimum Query

The minimum of a range, answered from O(log n) nodes of a min tree.

Range queries, algorithm, intermediateAlso called RMQ
Node 1 covers indices 0 to 7. Partly inside, so both children are checked.533171114462228current

Segment Tree: Minimum of indices 1 to 6

Decision, step 2 of 13

Node 1 covers indices 0 to 7, holding 1. That straddles the edge, so split into both children.

How segment tree works

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

Leads to

Topics that need this one first.

Taught by the same lesson

Segment Tree covers these too, in the same run.