Range Minimum Query

Range Minimum Query (RMQ) medium

Description

Support, over an array with point updates:

update(index, val) — set arr[index] = val.
queryMin(left, right) — return the minimum of arr[left..right].

Examples

> arr = [5, 2, 8, 1, 9]
  queryMin(1, 3)  -> 1        # min(2, 8, 1)
  update(3, 7)               # arr = [5, 2, 8, 7, 9]
  queryMin(1, 3)  -> 2        # min(2, 8, 7)

Constraints

1 <= arr.length <= 10^5, many interleaved queries/updates.

Intuition

Identical to the sum segment tree with two lines changed: the combine becomes min and the disjoint-case identity becomes +∞. Because min is associative, the tree works; because min is not invertible (you can’t subtract a min), a Fenwick tree is off the table — this is the problem that forces a segment tree.

Code (min segment tree)

This is the proof that the segment tree template is “generic over the aggregate.” The sum version and this min version differ only in combine (+ → min) and the identity returned for disjoint ranges (0 → +∞). Internalize that, and max-query, gcd-query, and OR-query are all the same code with a different two-character swap.

Analysis

Time: build O(n), update and queryMin O(log n).
Space: O(4n).

Static array, no updates? If the array never changes, you don’t even need a segment tree — a sparse table answers RMQ in O(1) per query after O(n log n) preprocessing. The segment tree earns its keep specifically when updates are present.

Same skin

Range Sum Query — Mutable — same skeleton, invertible aggregate (so a BIT also works).
Falling Squares — range-max queries with range updates (lazy).
Sliding Window Maximum (Day 24) — RMQ over a moving window, solved with a deque instead.

Range Sum Query — Mutable Range Addition