Implementing a Fenwick Tree for Range Queries

A Fenwick tree, also called a Binary Indexed Tree, is a compact data structure for maintaining cumulative values while an array changes. It supports prefix sums and point updates in logarithmic time, making it useful when a program needs many queries over a changing sequence.

This guide explains the internal bitwise trick, gives a Python implementation, and shows how to turn prefix sums into arbitrary range sums. The same approach applies to frequency counts, cumulative scores, inventory changes, and time-series data. For broader study, the data structures guide provides useful context around trees, arrays, and complexity analysis.

Fenwick Tree Basics

Suppose an array contains daily values:

[4, 2, 7, 1, 3, 6, 5, 8]

A prefix sum is the total from the beginning through a selected index. For example, the prefix sum through index 5 is 4 + 2 + 7 + 1 + 3 + 6 = 23. A range sum from index 3 to index 6 can be calculated as:

prefix_sum(6) - prefix_sum(2)

A simple prefix-sum array answers queries in constant time, but changing one original value requires updating every later prefix. That update costs O(n). A Fenwick tree balances these operations: both an update and a prefix query take O(log n) time, while storage remains O(n).

The structure stores partial sums rather than every possible interval. Each position is responsible for a block whose length is determined by its least significant set bit. For example, position 12 represents a block of four values because:

12 in binary = 1100
lowest set bit = 0100 = 4

This carefully selected grouping is what makes the data structure fast without the larger memory overhead of many interval structures.

Indexing And Core Operations

Fenwick trees are easiest to implement with one-based indexing. If the application array uses positions 0 through n - 1, the tree stores the corresponding values at positions 1 through n. The extra unused element at index zero is intentional because the update and query rules depend on one-based binary arithmetic.

The key expression is:

index += index & -index

The expression index & -index extracts the lowest set bit. During an update, adding that value moves to the next tree node that includes the changed position. During a prefix query, subtracting it moves towards the root-like collection of blocks:

index -= index & -index

For instance, if index is 12, the lowest set bit is 4. An update moves to 16, while a query moves from 12 to 8, then to 0. Each step removes or adds a binary block, so the number of steps is proportional to the number of bits in the array size.

A Clear Python Implementation

The class below supports construction, point updates, prefix sums, and inclusive range sums. The constructor starts with an empty tree and adds each initial value through the same update method used later. This keeps the logic easy to verify.

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

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

    def add(self, index, delta):
        """Add delta to the one-based position index."""
        while index <= self.n:
            self.tree[index] += delta
            index += index & -index

    def prefix_sum(self, index):
        """Return the sum of positions 1 through index."""
        total = 0

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

        return total

    def range_sum(self, left, right):
        """Return the inclusive sum from one-based left to right."""
        if left > right:
            return 0

        return self.prefix_sum(right) - self.prefix_sum(left - 1)

The add method accepts a delta, rather than a replacement value. If position 4 currently stores 10 and should become 13, call add(4, 3). If the new value is known directly, calculate delta = new_value - old_value before updating. This distinction is a common source of mistakes when moving from a normal array to a Fenwick tree.

Implementation Checks That Prevent Bugs

Allocate n + 1 elements so that position n is valid.
Convert zero-based application indexes to one-based tree indexes.
Use left - 1 when subtracting the prefix before an inclusive range.
Pass a difference to add, rather than the replacement value.
Reject or handle indexes outside the range expected by the class.

In production code, it is sensible to validate that 1 <= index <= n for updates and that query boundaries are valid. Competitive programming solutions often omit those checks for speed, but educational or business code benefits from clear errors.

Comparing Range Query Strategies

There is no universally best structure. A static dataset may favour a prefix array, while a changing dataset may need a Fenwick tree or segment tree. The right choice depends on whether updates are point-based, whether range updates are required, and how much query flexibility the application needs.

Structure	Point Update	Range Sum Query	Memory	Best Fit
Prefix-sum array	`O(n)`	`O(1)`	`O(n)`	Mostly static values
Fenwick tree	`O(log n)`	`O(log n)`	`O(n)`	Point updates and sums
Segment tree	`O(log n)`	`O(log n)`	`O(n)`	Flexible interval operations
Naive array scan	`O(1)`	`O(n)`	`O(n)`	Very few queries

A segment tree can represent minimums, maximums, greatest common divisors, and other operations that do not combine through subtraction as sums do. It is more general, but usually requires more code and approximately twice as much backing storage. A Fenwick tree is a strong choice when the operation is addition and the workload consists of point changes plus cumulative queries.

For a static report, such as a fixed list of yearly rainfall totals from the Bureau of Meteorology, a prefix array may be enough. For a live dashboard receiving new readings throughout the day, logarithmic updates avoid repeatedly rebuilding all later cumulative values.

Updating Values And Reading Ranges

Consider this example:

scores = [4, 2, 7, 1, 3, 6, 5, 8]
fenwick = FenwickTree(scores)

print(fenwick.range_sum(3, 6))  # 17
fenwick.add(4, 5)               # position 4 changes from 1 to 6
print(fenwick.range_sum(3, 6))  # 22

The original range from positions 3 through 6 is 7 + 1 + 3 + 6, which equals 17. Adding 5 to position 4 changes that range to 22. The tree updates only the partial-sum nodes that contain position 4; it does not scan the rest of the list.

It is useful to trace a small update by hand. An update at position 4 changes tree positions 4, 8, 16 and so on, stopping when the index exceeds the array length. A prefix query at position 6 visits positions 6, 4 and then 0. Those visited entries cover positions 1 through 6 without overlapping values.

The same method works for counts. If an online service records the number of customers arriving in each five-minute interval, adding one to an interval is a point update. The number of arrivals between two intervals is a range query. In an Australian setting, this could support a queue monitor for a busy Melbourne tram stop or a Sydney service centre during the afternoon peak.

Testing Correctness And Complexity

A reliable test suite should compare the Fenwick tree with a plain list. Generate small random arrays, apply random additions, and compare every requested range with Python’s direct sum:

expected = sum(values[left - 1:right])
actual = fenwick.range_sum(left, right)
assert actual == expected

Test boundaries carefully: the first position, the last position, a one-element interval, the complete array, and an empty interval if the API permits it. Also test negative deltas, since subtracting stock or correcting an overcount is a normal operation.

Cases Worth Testing

An empty input list and a single-element list.
Updates at positions 1 and n.
A range where left == right.
Several updates to the same position.
Negative values and negative update amounts.
Queries covering the full array after many changes.

Initialising through repeated add calls costs O(n log n). A specialised linear-time construction is possible by propagating each tree value to its parent, but the simpler constructor is often preferable unless the input is very large. Once built, every point update and prefix sum is O(log n), and a range sum performs two prefix queries, still O(log n) overall.

For memory, the tree uses n + 1 integers. It does not store every interval, so it is generally lighter than a segment tree. Python integers have object overhead, though, which matters for very large datasets. In memory-sensitive systems, an array module or a language such as C may provide a smaller representation.

Extending The Pattern

Fenwick trees can maintain frequencies and support order-statistic operations. If tree[i] stores how many items have a particular rank, a prefix sum tells how many items are at or below that rank. With a binary-lifting search, the structure can find the position of the k-th item in O(log n) time.

The technique can also support two-dimensional prefix sums, although a two-dimensional Fenwick tree requires O(nm) storage and nested update and query loops. This can be useful for changing grid data, such as counts by region and day. For more complicated range updates, variants using two Fenwick trees are available, but they require a careful derivation of the prefix formula.

Fenwick trees are especially practical in systems that process an event stream. A utility company might group electricity usage by half-hour interval, an agricultural platform near regional Queensland might track sensor readings, or a sports application might maintain cumulative player statistics. Australian developers should also account for daylight-saving differences between states when mapping timestamps to positions: the data structure handles indexes, while the application must define the time buckets consistently.

Clear explanations and tested implementations matter when a compact bitwise technique is introduced. The hello ML about page describes the community-oriented educational purpose behind publishing this kind of open programming material. Once the indexing convention and prefix-sum identity are understood, a Fenwick tree becomes a small, dependable tool for dynamic range queries.