Coding Interview: How do you build a lazy segment tree for range add and range sum?

Prompt and scope

Given an integer array of length n, process two online operations: add delta to every value in the closed interval [l, r], and return the sum of [l, r]. Target O(n) construction, O(log n) per operation, and O(n) extra space. State that intervals are closed, delta may be negative, and persistence is out of scope unless requested.

What the interviewer is testing

Write the invariant first: tree[p] is always the true sum for the node interval, while lazy[p] is a uniform increment already included in that sum but not yet applied to children. A strong answer updates a fully covered node only, pushes before partial traversal, and multiplies an increment by the covered length.

Clarifications before coding

1. Is the update add, assignment, or a range minimum? Their lazy-tag composition rules differ.
2. Is the aggregate a sum, minimum, or maximum? The node merge and tag formula change.
3. Are intervals closed? This answer uses closed [l, r]; half-open intervals require consistent splitting and lengths.
4. How large can values become? tree[p] + delta * length may overflow 32-bit integers, so choose a wider type.

Recommended solution and derivation

Store an implicit binary tree in arrays. A node [lo, hi] splits at mid into [lo, mid] and [mid+1, hi]. For a fully covered update, add delta * (hi-lo+1) to tree[p] and accumulate delta in lazy[p]; child values can remain untouched until needed.

class LazySumTree:
    def __init__(self, values):
        self.n = len(values)
        self.tree = [0] * (4 * max(1, self.n))
        self.lazy = [0] * len(self.tree)
        if self.n:
            self._build(1, 0, self.n - 1, values)

    def _apply(self, p, lo, hi, delta):
        self.tree[p] += delta * (hi - lo + 1)
        self.lazy[p] += delta

    def _push(self, p, lo, hi):
        if self.lazy[p] == 0 or lo == hi:
            return
        mid = (lo + hi) // 2
        d = self.lazy[p]
        self._apply(p * 2, lo, mid, d)
        self._apply(p * 2 + 1, mid + 1, hi, d)
        self.lazy[p] = 0

Complete add and sum recursively with the same invariant: call _apply on full coverage; call _push before partial coverage; recompute the parent from its children after returning. Each level visits only a constant number of boundary nodes, so updates and queries are O(log n) and storage is O(n).

Alternatives and trade-offs

For point updates plus prefix sums, a Fenwick tree is shorter and has smaller constants. For offline range additions followed by one final read, a difference array is simpler. A lazy segment tree earns its complexity when online range updates and range aggregates coexist. Range assignment needs an additional “has assignment” tag and an explicit precedence rule: assignment replaces an older assignment and add tag, while a later add accumulates after it.

Failure modes, boundaries, and counterexamples

• Forgetting interval length makes adding 3 to [2, 5] increase the sum by 3 instead of 12.
• Recursing after full coverage loses lazy propagation and may apply an update repeatedly.
• Failing to clear a tag after push applies the same increment again on the next visit.
• Not recomputing a parent after partial update leaves later full-cover queries stale.
• Mixing closed and half-open intervals causes one-element or mid+1 errors; validate an empty array, l > r, and n=0 at the boundary.

Tests and verification checklist

Use a naive array as an oracle, generate random updates and queries, and compare after every operation. Include one-element ranges, the full range, both boundaries, negative deltas, repeated overlap, and all-equal values. Assert that a parent equals the sum of its children after recursive calls, and check that the chosen integer type does not overflow on large inputs. Add an equivalence test if implementing an iterative layout.

Follow-up questions

How can range assignment and range add coexist?

Keep an optional assignment tag and an add tag per node. A new assignment replaces both older assignment and add; a new add accumulates after the assignment. Push assignment first and add second. The ordering is the correctness rule.

How do you support range minimum?

Store the interval minimum instead of sum; a range add still adds delta to that minimum, so the lazy tag remains simple. Range chmin or chmax requires richer invariants such as segment-tree beats.

How do you expose historical versions?

Use a persistent segment tree: copy nodes along the update path and share untouched subtrees. Each update copies about O(log n) nodes, and a root pointer identifies a version, so space grows with the number of updates.