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

Python Fenwick tree: update one amount and query prefix totals

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

A Fenwick tree stores partial sums so point updates and prefix-sum queries each visit logarithmically many nodes.

Download Python source kit

Operation contract

The owned ledger starts with three minor-unit amounts. The tree builds by adding each amount, reports the first two-item total, then increases the second amount by 25 and reports the new prefix and full totals. Public indexes are zero-based; internal tree indexes start at one. The wrapper rejects out-of-range positions before mutation.

Failure and ownership boundary

This structure answers prefix and range sums, not arbitrary minimum or maximum updates. Unbounded integer values can grow memory and arithmetic cost, so an import boundary should cap them. Python segment tree: point replacement and half-open range sums, Python lazy segment tree: defer interval additions and retain correct totals and NumPy floating-point checks: finite values and declared tolerances cover alternatives.

Working program

python
class PrefixLedger:
    def __init__(self, amounts):
        if type(amounts) is not list or not 1 <= len(amounts) <= 100 or any(type(value) is not int or not 0 <= value <= 1000 for value in amounts):
            raise ValueError("bounded amounts")
        self.size = len(amounts)
        self.tree = [0] * (self.size + 1)
        for index, amount in enumerate(amounts):
            self.add(index, amount)
    def add(self, index, delta):
        if type(index) is not int or not 0 <= index < self.size or type(delta) is not int or not -1000 <= delta <= 1000:
            raise ValueError("point update")
        position = index + 1
        while position <= self.size:
            self.tree[position] += delta
            position += position & -position
    def prefix(self, end):
        if type(end) is not int or not 0 <= end <= self.size:
            raise ValueError("exclusive end")
        total = 0
        while end:
            total += self.tree[end]
            end -= end & -end
        return total

ledger = PrefixLedger([125, 75, 50])
print(ledger.prefix(2))
ledger.add(1, 25)
print(ledger.prefix(2), ledger.prefix(3))

Output

Output
200
225 275

Costs and limits

Construction by repeated updates costs O(n log n) here; each later update or prefix query costs O(log n), with O(n) storage. A linear construction is possible but would need a separate checked fixture.

Common Mistakes

  • Do not mix zero-based public indexes with one-based tree positions.
  • A delta can make a stored amount negative; this fixture does not enforce per-item post-update bounds.

Connected lessons

Python segment tree: point replacement and half-open range sums, Python lazy segment tree: defer interval additions and retain correct totals, NumPy floating-point checks: finite values and declared tolerances.

python
fenwick-prefix-sums
Storage details