Medium · Iterative Segment Tree
Understand → Visualise → Practice.
Return the minimum value in each inclusive `[left,right]` query over a non-empty immutable array.
Place the leaves at a power-of-two offset. Climbing from both ends, take a node whenever it is a right child on the left boundary or a left child on the right boundary.
Round the size up to a power of two, copy values into tree[size + i], and fill parents with min(left, right).
Shift l and r by size. If l is odd, take tree[l] and move l right; if r is even, take tree[r] and move r left; then halve both.
When l > r every part of the range has been counted; return the smallest value taken.
O(n) construction and O(log n) per query, with O(n) space.
Mixing inclusive and half-open bounds causes missed endpoints.
Read the full guide first: Fenwick Trees and Segment Trees.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.