Logarithmic Range Processing (Handling Range Queries/Updates in O(log N))

Segment trees achieve O(log n) per range operation because the tree height is logarithmic and each query touches O(log n) nodes.

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)

Recurrence: T(n)=2T(n/2)+O(1) for a single path—at most two children per level along the interval boundary.

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

• Claiming O(1) range query without structure.
• O(n) height skewed tree (not a proper segment tree).

Key takeaways

• Compare with O(n) brute force to feel the win at n=10⁵, q=10⁵.
• Fenwick also O(log n) but only for invertible sums.