Python lazy segment tree: defer interval additions and retain correct totals

Last updated: 30 Sept 20264 min read

tutorial

A lazy sum tree records a pending interval addition so a covered subtree can update its total without immediately visiting every leaf.

Download Python source kit

Operation contract

The ledger owns bounded integer amounts and uses half-open ranges. Applying a delta to an interval changes its sum by interval length times delta. A partial query or update pushes that pending delta into children before descending. Empty intervals are valid and do no work. Point replacement is a different operation from these interval additions.

Failure and ownership boundary

Pushing changes internal bookkeeping even during a query, so this tree is not a lock-free immutable snapshot. Invalid indexes and boolean deltas are rejected before any tree change. Arbitrarily large integers remain valid but have digit-dependent arithmetic costs. Python segment tree: point replacement and half-open range sums and Python locks: protect the complete inventory transition address the other contracts.

Working program

class RangeAmounts:
    def __init__(self, amounts):
        if not 1 <= len(amounts) <= 128 or any(type(amount) is not int for amount in amounts):
            raise ValueError("bounded integer amounts required")
        self.count = len(amounts)
        self.sums = [0] * (4 * self.count)
        self.lazy = [0] * (4 * self.count)
        def build(position, left, right):
            if right - left == 1:
                self.sums[position] = amounts[left]
                return
            middle = (left + right) // 2
            build(position * 2, left, middle); build(position * 2 + 1, middle, right)
            self.sums[position] = self.sums[position * 2] + self.sums[position * 2 + 1]
        build(1, 0, self.count)
    def _validate(self, left, right):
        if any(type(index) is not int for index in (left, right)) or not 0 <= left <= right <= self.count:
            raise ValueError("invalid half-open interval")
    def _apply(self, position, length, delta):
        self.sums[position] += length * delta
        self.lazy[position] += delta
    def _push(self, position, left, right):
        if self.lazy[position] and right - left > 1:
            middle = (left + right) // 2
            self._apply(position * 2, middle - left, self.lazy[position])
            self._apply(position * 2 + 1, right - middle, self.lazy[position])
            self.lazy[position] = 0
    def add(self, left, right, delta):
        self._validate(left, right)
        if type(delta) is not int:
            raise ValueError("integer delta required")
        def change(position, start, end):
            if right <= start or end <= left:
                return
            if left <= start and end <= right:
                self._apply(position, end - start, delta)
                return
            self._push(position, start, end)
            middle = (start + end) // 2
            change(position * 2, start, middle); change(position * 2 + 1, middle, end)
            self.sums[position] = self.sums[position * 2] + self.sums[position * 2 + 1]
        if left != right:
            change(1, 0, self.count)
    def total(self, left, right):
        self._validate(left, right)
        def query(position, start, end):
            if right <= start or end <= left:
                return 0
            if left <= start and end <= right:
                return self.sums[position]
            self._push(position, start, end)
            middle = (start + end) // 2
            return query(position * 2, start, middle) + query(position * 2 + 1, middle, end)
        return query(1, 0, self.count) if left != right else 0

ledger = RangeAmounts([1, 3, 5, 7])
print(ledger.total(0, 4))
ledger.add(1, 3, 2)
print(ledger.total(0, 4))
print(ledger.total(2, 3))
print(ledger.total(2, 2))

Output

Costs and limits

Construction uses O(n) time and storage. An accepted interval addition or sum query performs O(log n) tree work under its lazy invariant, with O(log n) recursion depth. It does not provide persistence, concurrent snapshots or crash durability.

Common Mistakes

Scale a covered sum update by interval length.
Push pending state before reading partially covered child totals.

Connected lessons

Python segment tree: point replacement and half-open range sums, Python locks: protect the complete inventory transition, Python range exercise: immutable prefix totals and exclusive endpoints.

python

lazy-range-sums