Implementing a Fenwick Tree in Python

A Fenwick tree, also called a Binary Indexed Tree, is a compact data structure for maintaining cumulative values while data changes. It supports prefix-sum queries and point updates in logarithmic time, making it useful when an ordinary array is too slow and a full segment tree would be unnecessary.

Suppose an application stores daily sales, scores, transaction counts, or frequency values. A prefix sum asks for the total from the beginning through a chosen index. With a static array, prefix sums can be precomputed in linear time, but changing one value may require rebuilding every later total. A Fenwick tree avoids that cost by storing overlapping partial sums.

The technique fits naturally beside other algorithmic tools. The algorithm collection includes broader examples of searching, graphs, and optimisation, while this data structure focuses on a particularly useful pattern: fast cumulative queries over mutable numeric data.

Why Prefix Sums Need Structure

For an array such as [3, 2, 7, 1, 6], the prefix sum at index 3 is 3 + 2 + 7 + 1 = 13. If the array never changes, a prefix-sum array is ideal. We can build it once and answer each query in constant time. However, changing the value at index 1 from 2 to 9 affects every prefix beginning at index 1.

Updating a normal prefix-sum array can therefore take O(n) time. Repeating this operation for many updates leads to quadratic behaviour. A Fenwick tree distributes the values across partial ranges, so one changed element touches only a logarithmic number of stored totals. Each query also combines a logarithmic number of those ranges.

This makes the structure valuable in problems involving frequencies, rankings, inversion counts, running totals, and online statistics. It is especially suitable when updates affect individual positions and queries ask for totals from index zero or one through a selected position.

Reading The Binary Layout

The central operation is the least significant set bit, commonly written as lowbit(i). In Python, it is calculated with:

lowbit = i & -i

For example, lowbit(12) is 4, because the binary representation of 12 is 1100. A Fenwick tree uses this value to determine the size of the range represented by position i. Position 12 stores a total covering four original elements, while position 8 stores a total covering eight elements.

The internal array is conventionally one-based, even when the source data uses zero-based indexing. For index i, the update operation moves to i + lowbit(i), travelling towards larger positions. A prefix query moves to i - lowbit(i), stripping away the lowest set bit and combining stored ranges.

This binary movement is related to the same divide-and-combine thinking found in graph and dynamic programming algorithms. For a different perspective on structured algorithmic reasoning, a Prim's algorithm guide shows how carefully chosen local structures can produce an efficient global result.

Building A Python Implementation

A practical class stores the number of elements and an internal list with one extra slot. The public methods can accept zero-based indexes, which are more familiar to Python programmers, while the private storage remains one-based.

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

        for index, value in enumerate(values):
            self.add(index, value)

    def add(self, index, delta):
        if index < 0 or index >= self.n:
            raise IndexError("index out of range")

        position = index + 1
        while position <= self.n:
            self.tree[position] += delta
            position += position & -position

    def prefix_sum(self, index):
        if index < 0:
            return 0
        if index >= self.n:
            index = self.n - 1

        total = 0
        position = index + 1
        while position > 0:
            total += self.tree[position]
            position -= position & -position
        return total

The constructor begins with zeros and adds each input value. This is easy to read and costs O(n log n). A specialised linear-time construction is possible, but the repeated-update version is often preferable in teaching code because it directly demonstrates how the data structure works.

The add method receives a change, rather than a replacement value. If an element currently equals 10 and should become 14, call add(index, 4). Keeping this distinction clear prevents a common bug in which the new value is added on top of the old value without first calculating the difference.

Updating And Querying Values

To retrieve the total from index zero through index r, call prefix_sum(r). The method repeatedly adds the range represented by the current internal position and then moves backwards using the least significant set bit. When the position reaches zero, all required ranges have been included.

values = [3, 2, 7, 1, 6]
fenwick = FenwickTree(values)

print(fenwick.prefix_sum(3))  # 13

fenwick.add(1, 7)             # 2 becomes 9
print(fenwick.prefix_sum(3))  # 20

A range sum can be calculated by subtracting two prefix sums. For a zero-based inclusive interval [left, right], the formula is:

def range_sum(fenwick, left, right):
    if left > right:
        return 0
    before_left = fenwick.prefix_sum(left - 1)
    return fenwick.prefix_sum(right) - before_left

The subtraction works because the prefix through right contains both the desired interval and everything before left. Removing the prefix through left - 1 leaves exactly the requested range. This method also handles left == 0, because a negative prefix index returns zero.

Complexity And Design Choices

Each update or prefix query visits at most O(log n) positions. The tree uses O(n) additional memory, and constructing it through repeated calls to add takes O(n log n). For a fixed input array, a linear construction can reduce build time, but it does not change the cost of later operations.

A Fenwick tree is simpler and usually more memory-efficient than a segment tree when the required operation is an invertible prefix aggregate such as sum. It can also support frequencies, minimum values in restricted designs, and other associative operations with suitable adaptations. A segment tree is more flexible for arbitrary interval operations, range updates, or queries that need richer information.

The choice depends on the workload. A static prefix array is faster for reads and uses less logic when updates are absent. A Fenwick tree is a strong middle ground for frequent point changes and cumulative queries. In competitive programming, it is often the first structure to consider for online inversion counting or order-statistics problems.

Practical Uses In Australian Data

Consider a transport analysis project using daily tap-on or ticket-validation counts from Sydney’s Opal system or Melbourne’s Myki network. A Fenwick tree could maintain passenger totals by time slot while late-arriving corrections update individual intervals. A query for all validations up to a particular hour would remain logarithmic instead of scanning the complete day.

The same pattern applies to Australian market data. An analyst might maintain counts of trades across ASX price bands, update a band when a new transaction arrives, and calculate how many trades occurred below a selected price. Frequency tables can also support ranking and percentile-style calculations when values are mapped to discrete positions.

Privacy requirements matter when data comes from identifiable travel, financial, or customer records. Under the Privacy Act 1988, systems should be designed with appropriate handling and protection of personal information. A Fenwick tree does not provide privacy by itself; it is simply an efficient aggregation layer, so developers still need to minimise collected data and avoid exposing individual records.

Another everyday example is household electricity analysis. Australian electricity bills commonly use time-based usage data, and a program could maintain cumulative consumption across half-hour intervals while corrections arrive from a meter feed. For event-ledger experiments, a simple blockchain tutorial provides useful Python context; a Fenwick tree could separately track cumulative transaction amounts, although it would not replace the ledger’s validation or consensus mechanisms.

Testing Extensions And Common Mistakes

Tests should compare every Fenwick result with a straightforward list calculation. After each random update, calculate the expected prefix with sum(values[:index + 1]) and compare it with prefix_sum(index). Testing empty arrays, one-element arrays, negative values, repeated updates, and queries at the first and last positions exposes most indexing errors.

The most frequent mistake is mixing zero-based public indexes with one-based internal positions. Another is passing a new value to add instead of the difference between the new and old values. Off-by-one errors also appear when calculating a range: prefix_sum(left - 1) must be removed, not prefix_sum(left).

The structure can be extended with a get(index) method by subtracting adjacent prefixes, or with a lower_bound(target) method that finds the first position whose cumulative frequency reaches a target. The latter is useful when the tree stores non-negative counts, such as the number of items in sorted categories. These extensions preserve the compact binary layout while supporting more advanced queries.