Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Python segment tree: point replacement and half-open range sums

Last updated: 30 Sept 20264 min read
tutorial
IntermediateBy AITrove Editorial

A sum segment tree stores interval totals so a point replacement or range query need not rescan the entire sequence.

Download Python source kit

Operation contract

The ledger accepts exact integers and owns a separate tree array. Queries use half-open ranges: the left index is included and the right index is excluded. An empty range returns zero. Replacing a point updates its leaf and every ancestor total; it does not add a delta to an already changed value.

Failure and ownership boundary

The fixture bounds the initial list and rejects boolean values or invalid ranges before mutation. It supports point replacement only. Interval addition needs lazy propagation or a different representation. Concurrent readers need coordination if replacement can occur during a query. Python lists: slicing copies the outer sequence, not nested objects and Python locks: protect the complete inventory transition explain what the tree alone does not provide.

Working program

python
class LedgerSums:
    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.tree = [0] * (2 * self.count)
        self.tree[self.count:] = amounts
        for index in range(self.count - 1, 0, -1):
            self.tree[index] = self.tree[2 * index] + self.tree[2 * index + 1]
    def replace(self, index, amount):
        if type(index) is not int or not 0 <= index < self.count or type(amount) is not int:
            raise ValueError("invalid replacement")
        position = index + self.count
        self.tree[position] = amount
        while position > 1:
            position //= 2
            self.tree[position] = self.tree[2 * position] + self.tree[2 * position + 1]
    def total(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")
        left += self.count
        right += self.count
        amount = 0
        while left < right:
            if left % 2:
                amount += self.tree[left]
                left += 1
            if right % 2:
                right -= 1
                amount += self.tree[right]
            left //= 2
            right //= 2
        return amount

ledger = LedgerSums([125, 250, 75, 50])
print(ledger.total(1, 4))
ledger.replace(2, 100)
print(ledger.total(0, 4))
print(ledger.total(2, 2))

Output

Output
375
525
0

Costs and limits

Building n leaves costs O(n) time and O(n) storage. A replacement and a range query each cost O(log n) tree operations, excluding arbitrary-size integer arithmetic. The private array is a teaching convention, not a tamper-proof access boundary.

Common Mistakes

  • Keep the right endpoint exclusive.
  • Point replacement is not range addition.

Connected lessons

Python lists: slicing copies the outer sequence, not nested objects, Python binary search: use a half-open interval and require sorted input, Python locks: protect the complete inventory transition.

Follow the related contract

Python lazy segment tree: defer interval additions and retain correct totals, Python range exercise: immutable prefix totals and exclusive endpoints.

Trace the next boundary

Python Fenwick tree: update one amount and query prefix totals.

python
segment-tree
Storage details