Range Update

Range update changes every a[i] for l≤i≤r—naive O(n) per update fails; use lazy segment tree, difference array, or sqrt decomposition.

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)

Range add + point query: difference array. Range add + range sum: lazy propagation. Range assign: lazy with assignment tag.

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

• Using point-update loop O(n·q).
• Difference array when you need range sum query (need prefix + lazy or segtree).

Key takeaways

• Match update+query pair to known template.
• Draw lazy tags on a tiny tree.