Lazy segment tree: add to a range and query its minimum

Last updated: 5 Oct 20269 min read

tutorial

A lazy segment tree stores an aggregate for each interval plus an update that has not yet been pushed to its children. Here the aggregate is the minimum and the deferred operation adds the same integer to every value in a covered half-open range. Adding a constant changes that interval's minimum by the same constant, so a fully covered node can update its own minimum and pending amount without touching descendants. Before a partial descent, push moves the pending amount into both children and clears the parent's marker. The visible node minimum remains current throughout. An empty update changes nothing; an empty minimum query is rejected because it has no numeric answer.

Operational case

Start with capacities 61, 47, 83, 26, 52, and 19. Subtract 7 from positions [1, 5), making the full-range minimum 19. Add 20 over [3, 6); the minimum in [2, 6) becomes 39, while [0, 3) still has minimum 40. Both updates overlap at positions 3 and 4, so their deferred amounts must compose by addition. This code deliberately handles range addition, not assignment. An assignment marker would need a separate overwrite rule; treating it as another increment would give wrong values after overlapping operations.

Working Python program

"""Half-open range additions and minimum queries with deferred updates."""


class CapacityMinimums:
    def __init__(self, capacities: list[int]):
        if not capacities:
            raise ValueError("capacities must be nonempty")
        self.length = len(capacities)
        self.minimum = [0] * (4 * self.length)
        self.pending_add = [0] * (4 * self.length)

        def build(node: int, low: int, high: int) -> None:
            if high - low == 1:
                self.minimum[node] = capacities[low]
                return
            middle = (low + high) // 2
            build(node * 2, low, middle)
            build(node * 2 + 1, middle, high)
            self.minimum[node] = min(self.minimum[node * 2], self.minimum[node * 2 + 1])

        build(1, 0, self.length)

    def _push(self, node: int) -> None:
        amount = self.pending_add[node]
        if amount:
            for child in (node * 2, node * 2 + 1):
                self.minimum[child] += amount
                self.pending_add[child] += amount
            self.pending_add[node] = 0

    def add_between(self, start: int, stop: int, amount: int) -> None:
        if not 0 <= start <= stop <= self.length:
            raise IndexError((start, stop))

        def change(node: int, low: int, high: int) -> None:
            if stop <= low or high <= start:
                return
            if start <= low and high <= stop:
                self.minimum[node] += amount
                self.pending_add[node] += amount
                return
            self._push(node)
            middle = (low + high) // 2
            change(node * 2, low, middle)
            change(node * 2 + 1, middle, high)
            self.minimum[node] = min(self.minimum[node * 2], self.minimum[node * 2 + 1])

        change(1, 0, self.length)

    def minimum_between(self, start: int, stop: int) -> int:
        if not 0 <= start < stop <= self.length:
            raise IndexError((start, stop))

        def query(node: int, low: int, high: int) -> int | None:
            if stop <= low or high <= start:
                return None
            if start <= low and high <= stop:
                return self.minimum[node]
            self._push(node)
            middle = (low + high) // 2
            left = query(node * 2, low, middle)
            right = query(node * 2 + 1, middle, high)
            if left is None:
                return right
            if right is None:
                return left
            return min(left, right)

        return query(1, 0, self.length)


capacity_index = CapacityMinimums([61, 47, 83, 26, 52, 19])
capacity_index.add_between(1, 5, -7)
print(capacity_index.minimum_between(0, 6))
capacity_index.add_between(3, 6, 20)
print(capacity_index.minimum_between(2, 6))
print(capacity_index.minimum_between(0, 3))

Output

19
39
40

Time, space, and tradeoff

For N initial values, construction takes O(N) time and uses O(N) minimum and pending storage. A range addition or nonempty minimum query visits O(log N) boundary branches in a segment-tree decomposition, with O(log N) recursion depth. The implementation's query may push pending markers and therefore mutate internal representation while preserving logical values. A flat array makes updates over K elements O(K) and scans of a K-element range O(K), often a better choice for tiny workloads. This index does not resize; adding a new capacity position requires a rebuild or another representation.

Common Mistakes

Do not forget to push a pending amount before entering only one child.
Do not combine minimums using addition after a partial update.
Do not treat an empty range as having an ordinary minimum.
Do not reuse the add marker for range assignment without changing composition rules.

Connected lessons

Apply the invariant in the warehouse indexes project, then check the operations quiz.

Two Fenwick trees: add across ranges and query sums adds a related operation contract.

Segment tree beats: cap a range while retaining its sum adds a distinct structure contract to compare.

Affine lazy segment trees: compose range calibration before summing examines a related structure with a different operation boundary.

data structures

range-query-structures