Advanced Segment Tree (Lazy Propagation, Range Updates & Complex Queries)

Advanced segment trees combine multiple techniques: lazy propagation, custom monoid, beats (range min with range add), or matrices on 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)

Interview “hard” segtree problems usually mean non-standard merge or tricky lazy—still O(log n) if each node stores constant-size summary.

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

• Copying library code without understanding push order.
• Segment tree beats without proof (rare in interviews).

Key takeaways

• Master lazy sum + assign first.
• Read one “segment tree beats” editorial after basics.