Range Minimum Query

RMQ (range minimum query) on a changing array needs a segment tree or balanced BST; static RMQ can use sparse table in O(1).

Why this shows up in the real world

Time-series dashboards, game leaderboards, and competitive programming interval problems all need fast answers on changing arrays.

Core idea (explained for students)

Segment tree min query is O(log n) per query with O(log n) point update—good default when values change.

Try this in Python

class SegTreeMin:
    INF = 10**18

    def __init__(self, arr: list[int]) -> None:
        self.n = len(arr)
        self.size = 1
        while self.size < self.n:
            self.size *= 2
        self.t = [self.INF] * (2 * self.size)
        for i, x in enumerate(arr):
            self.t[self.size + i] = x
        for i in range(self.size - 1, 0, -1):
            self.t[i] = min(self.t[2 * i], self.t[2 * i + 1])

    def query(self, l: int, r: int) -> int:
        l += self.size
        r += self.size
        ans = self.INF
        while l <= r:
            if l % 2 == 1:
                ans = min(ans, self.t[l])
                l += 1
            if r % 2 == 0:
                ans = min(ans, self.t[r])
                r -= 1
            l //= 2
            r //= 2
        return ans


print(SegTreeMin([4, 2, 7, 1, 9]).query(0, 3))

Common mistakes

• Using sum tree for min.
• Sparse table with updates (does not work without rebuild).

Key takeaways

• Sparse table: O(n log n) build, O(1) query, static only.
• Segment tree: dynamic.