Segment Tree Basics

Segment trees store an array in a binary tree so any interval [l,r] can be aggregated (sum, min, gcd, …) in O(log n) after O(n) build.

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)

Use a complete binary tree on indices 0..n-1. Leaves hold array values; each internal node combines its two children with an associative operation. Iterative 1-indexed arrays (size = next power of two) are common in contests.

Try this in Python

class SegTreeSum:
    def __init__(self, arr: list[int]) -> None:
        self.n = len(arr)
        self.size = 1
        while self.size < self.n:
            self.size *= 2
        self.t = [0] * (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] = self.t[2 * i] + self.t[2 * i + 1]

    def update(self, i: int, val: int) -> None:
        i += self.size
        self.t[i] = val
        while i > 1:
            i //= 2
            self.t[i] = self.t[2 * i] + self.t[2 * i + 1]

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


st = SegTreeSum([1, 3, 5, 7, 9, 11])
print(st.query(1, 4))
st.update(2, 10)
print(st.query(1, 4))

Common mistakes

• Building with wrong size (must be ≥ n, usually power of two).
• Forgetting that updates/queries need 0-based leaf indices consistently.

Key takeaways

• Draw the tree for n=4 once; label leaves and internal sums.
• Only use segment trees when you have many interval queries—not for one-off prefix sums.