Persistent Segment Tree with Lazy Propagation

Persistent + lazy is expert-level: lazy tags on cloned nodes—push must copy children before applying lazy to preserve old versions.

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)

Rare in interviews unless company is hardcore CP—know conceptually after plain persistent and plain lazy.

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

• Applying lazy to shared child without copy.
• Memory limits on many versions.

Key takeaways

• Implement persistent without lazy first.
• Each push allocates new child nodes.