Range Update + Range Query (Lazy Segment Tree Pattern)

The classic range update + range query pair (e.g., add v to [l,r], ask sum on [l,r]) is the standard lazy segment tree interview template.

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)

Maintain sum and lazy_add per node. Range add fully covers node → update sum and lazy tag. Query pushes lazy before visiting children.

Try this in Python

class LazyRangeAdd:
    def __init__(self, n: int) -> None:
        self.n = n
        self.size = 1
        while self.size < n:
            self.size *= 2
        self.sum = [0] * (2 * self.size)
        self.lazy = [0] * (2 * self.size)

    def _push(self, i: int, seg_l: int, seg_r: int) -> None:
        if self.lazy[i] == 0:
            return
        mid = (seg_l + seg_r) // 2
        length = mid - seg_l + 1
        self.lazy[2 * i] += self.lazy[i]
        self.lazy[2 * i + 1] += self.lazy[i]
        self.sum[2 * i] += self.lazy[i] * length
        self.sum[2 * i + 1] += self.lazy[i] * (seg_r - mid)
        self.lazy[i] = 0

    def range_add(self, ql: int, qr: int, val: int) -> None:
        self._add(1, 0, self.size - 1, ql, qr, val)

    def _add(self, i: int, l: int, r: int, ql: int, qr: int, val: int) -> None:
        if qr < l or r < ql:
            return
        if ql <= l and r <= qr:
            self.lazy[i] += val
            self.sum[i] += val * (r - l + 1)
            return
        self._push(i, l, r)
        mid = (l + r) // 2
        self._add(2 * i, l, mid, ql, qr, val)
        self._add(2 * i + 1, mid + 1, r, ql, qr, val)
        self.sum[i] = self.sum[2 * i] + self.sum[2 * i + 1]

    def range_sum(self, ql: int, qr: int) -> int:
        return self._query(1, 0, self.size - 1, ql, qr)

    def _query(self, i: int, l: int, r: int, ql: int, qr: int) -> int:
        if qr < l or r < ql:
            return 0
        if ql <= l and r <= qr:
            return self.sum[i]
        self._push(i, l, r)
        mid = (l + r) // 2
        return self._query(2 * i, l, mid, ql, qr) + self._query(2 * i + 1, mid + 1, r, ql, qr)


lz = LazyRangeAdd(6)
lz.range_add(1, 3, 5)
print(lz.range_sum(0, 5))

Common mistakes

• Forgetting to multiply lazy add by segment length when updating sum.
• Not clearing lazy after push.

Key takeaways

• Code range_add and range_sum together, test interleaved.
• Assignment lazy is a different push (overwrite children).