Understanding the Fenwick tree for dynamic prefix sums

A prefix sum answers a simple question: how much has accumulated up to a particular position? Given daily sales, rainfall readings or energy use, the total across indices 1 through k becomes useful when a dashboard needs a running balance, a cumulative average, or the difference between two points in time. The difficulty appears when values change after earlier results have already been calculated.

A Fenwick tree, also called a binary indexed tree, maintains these answers while individual entries are updated. Instead of rebuilding an entire prefix-sum array after each change, it stores a carefully chosen set of partial totals and revisits only the summaries affected by that update. The result is logarithmic work per operation, with a compact representation that suits languages and systems where memory matters.

Consider live infrastructure rather than an abstract example. A Melbourne operator may want running footfall near railway and tram stops. A Sydney energy analyst may need cumulative household electricity demand, while a Brisbane application can summarise Bureau of Meteorology rainfall observations. These workloads combine frequent point updates with repeated questions about totals from the beginning of a sequence.

Similar requirements appear in business software. A Perth mining dashboard might add shipment tonnage to a dated sequence and ask for production accumulated during a shift. A Fenwick tree turns those queries into fast prefix lookups without assuming that the underlying values are permanent. Its restrictions matter, though: it excels at indexed prefix totals, not every imaginable range calculation.

Why prefix sums become dynamic

Suppose an Adelaide market stall records takings in Australian dollars across fifteen-minute trading intervals. Totals include Australian GST, and each interval may later be corrected when a payment is refunded or a cash order is entered. A conventional prefix-sum array can answer each question immediately, but changing interval 8 invalidates every prefix that includes it.

A Fenwick tree avoids that cascade. It retains totals for blocks of intervals, so an adjustment to interval 8 updates only the blocks containing that entry. Queries still walk through a small sequence of block totals. The data structure therefore captures the best part of the prefix-sum array—quick reads—while reducing the penalty for frequent writes.

This is a dynamic prefix-sum problem, but it is not synonymous with a general-purpose database index. The sequence is logically ordered, contributions are added at known positions, and the natural question is “how much came before this point?” Those assumptions let the tree use integer arithmetic and predictable traversal paths rather than maintaining complex linked records.

The binary indexed tree invariant

The central idea is the lowbit operation. For a positive index i, lowbit(i) is the value of its least significant set bit, computed in ordinary two’s-complement arithmetic as i & -i. It equals the largest power of two dividing i and determines the size of the block represented at that position.

At index i, the tree stores the sum of values in the inclusive interval [i - lowbit(i) + 1, i]. For example, tree[8] covers 1 through 8, tree[12] covers 9 through 12, and tree[6] covers 5 through 6. Each stored block ends at its own index and has a length that is a power of two.

Those blocks overlap, which is the source of the tree’s efficiency. A prefix query never needs every stored total; it selects the blocks that partition the requested range exactly. An update changes one value, then adds the same delta to every stored block containing it. The structure is sometimes pictured as layers of blocks with sizes 1, 2, 4, 8 and so on.

Updates and queries in logarithmic time

A prefix query for index k follows a simple route. Starting at k, add tree[k], subtract lowbit(k) from k, and repeat until k becomes zero. With positions numbered from 1, a query at 13 visits 13, 12 and 8: their blocks cover 13, 9 through 12, and 1 through 8.

A point update follows the complementary route. To add delta at position p, add it to tree[p], set p to p + lowbit(p), and continue while p is within the array. The visited positions are exactly the summaries affected by the change. Each route has logarithmic length because every step removes or skips a set bit.

Unlike probabilistic skip lists, which accelerate ordered searches through extra levels of links, a Fenwick tree organises partial sums within a fixed array. The distinction matters when choosing a structure: a skip list answers search and ordering questions, whereas this tree answers additive questions about a known numeric sequence.

A compact Python implementation

The following Python implementation uses a one-based internal array, matching the mathematical explanation. The constructor accepts ordinary zero-based Python sequences but translates them into the tree’s one-based indexing. It also performs an O(n) build rather than repeatedly calling the update method for every value.

class FenwickTree:
    def __init__(self, values):
        self.n = len(values)
        self.tree = [0] * (self.n + 1)

        for i, value in enumerate(values, start=1):
            self.tree[i] += value
            parent = i + (i & -i)
            if parent <= self.n:
                self.tree[parent] += self.tree[i]

    def add(self, index, delta):
        while index <= self.n:
            self.tree[index] += delta
            index += index & -index

    def prefix_sum(self, index):
        total = 0
        while index > 0:
            total += self.tree[index]
            index -= index & -index
        return total

    def range_sum(self, left, right):
        return self.prefix_sum(right) - self.prefix_sum(left - 1)

The update method changes a single position, and prefix_sum returns the total from position 1 through the requested index. range_sum then subtracts two prefixes to obtain an arbitrary inclusive interval. This is safe because sums are additive: the total through right minus the total before left leaves exactly the values in between.

Calling prefix_sum(0) correctly returns zero because the loop never runs. Empty input produces a tree with no elements, and callers must reject updates or positive queries until a valid position exists. The implementation assumes numeric values that can be added; integers are the simplest case, while fractional monetary amounts can use integer cents or Decimal values.

Propagation, dependencies, and careful updates

An update propagates a local change to a bounded set of dependent summaries, much as neural network backpropagation distributes errors through connected computation layers. The analogy is useful, not identical: tree propagation simply adds the same delta to selected ancestors, with no learning rate, activation function or gradient calculation involved.

Negative contributions are perfectly valid because the tree does not assume that every value is positive. A refund can subtract money, and a rainfall series may record a negative adjustment after recalibration. As long as the sum operation is associative and commutative, block totals remain correct.

Care is still needed around the interface. Validate indices before accessing the internal list, define what happens for reversed ranges, and keep the tree’s indexing convention consistent across the codebase. If values are mutable objects, ensure their numeric contribution is captured correctly when an update is requested. A Fenwick tree summarises numbers; it does not track changes inside arbitrary records.

Choosing the right data structure

A Fenwick tree is a strong fit when updates are frequent, queries ask for prefixes, and the full sequence fits in memory. It can support both point increments and arbitrary interval totals, with O(log n) time per operation and O(n) storage. The one-based implementation also makes it convenient to mirror mathematical notation.

Segment trees become preferable when operations such as range assignment, range minimum or a more complicated lazy update dominate the workload. For database workloads centred on arbitrary indexed ranges, B-tree range queries offer a different trade-off between tree height, fan-out and storage layout. Those structures answer a broader family of questions, while the Fenwick tree stays focused and lean.

Fixed query patterns can also affect the choice. If an application always asks for one moving total, specialised aggregation may be simpler. If it must combine many prefix queries with historical snapshots, persistence or another design may be needed. The key is to measure which operations occur and avoid paying for general flexibility that the application never uses.

Practical guidance for reliable implementations

Reliable implementations benefit from a few concrete habits. They make the indexing rule explicit, test the boundary between two adjacent ranges, and distinguish an empty result from an invalid request. Benchmarking should include both updates and queries because improving one operation can accidentally slow the other.

• Choose a one-based or zero-based API deliberately, and keep that convention consistent in tests and documentation.
• Test prefix sums at zero, at the final index, and immediately after updates to the first and last positions.
• Check the invariant that each tree entry equals the sum of its represented block after every update.
• Use integer minor units for money so that decimal rounding does not accumulate unnoticed errors.
• Validate out-of-range positions and define behaviour for reversed intervals before exposing a public method.
• Benchmark realistic update and query mixes, including frequent changes near the beginning of the sequence.

Once these conventions are settled, the tree offers a dependable balance of clarity and speed. It supports live cumulative reporting for Melbourne footfall, Brisbane rainfall and Perth shipment records without forcing every query to scan the source data. That combination of predictable complexity, modest memory use and straightforward code makes it a valuable tool in the standard programming toolkit.