Segment Tree Min Query

Range minimum swaps + for min and 0 for +∞ in the combine step—same tree shape, different monoid.

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)

Point updates set a leaf then bubble min(childL, childR) upward. For static RMQ only, sparse table can be simpler; segment trees win 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

• Initializing internal nodes to 0 instead of infinity breaks min queries.
• Updating without rebubbling min values.

Key takeaways

• Keep INF as a module-level constant larger than any array value.
• Test query on a single element [i,i].