Fenwick Tree

A Fenwick tree, also called a binary indexed tree, supports efficient prefix queries and point updates.

It is often used for prefix sums that must handle updates.

Core Idea

The structure stores partial sums whose lengths are determined by binary patterns in the index. A prefix query combines a small number of these stored partial sums.

Both point update and prefix sum query are O(log n).

Class Contract

FenwickTree(size) creates a structure for zero-based public indexes 0 through size - 1.

add(index, delta) adds delta to one position. prefix_sum(index) returns the sum from 0 through index. The helper range_sum(tree, left, right) subtracts prefix sums to answer an inclusive range query.

Python Example

class FenwickTree:
    def __init__(self, size):
        self.tree = [0] * (size + 1)
 
    @classmethod
    def from_values(cls, values):
        result = cls(len(values))
        for index, value in enumerate(values):
            result.add(index, value)
        return result
 
    def add(self, index, delta):
        index += 1
        while index < len(self.tree):
            self.tree[index] += delta
            index += index & -index
 
    def prefix_sum(self, index):
        index += 1
        total = 0
        while index > 0:
            total += self.tree[index]
            index -= index & -index
        return total

The public indexes are zero-based, while the internal tree uses one-based indexing. from_values builds a tree by adding each input value.

Range Sum

A Fenwick tree usually answers range sums by subtracting prefix sums:

def range_sum(tree, left, right):
    return tree.prefix_sum(right) - (
        tree.prefix_sum(left - 1) if left > 0 else 0
    )

The structure stores enough information to answer prefix queries quickly.

The Lowbit Step

The expression:

index & -index

extracts the lowest set bit. In a Fenwick tree, that value controls how far the index jumps to reach the next responsible range.

You do not need to memorize the binary proof first, but you should know that the jumps are what make the operation logarithmic.

Complexity

Construction by repeated add is O(n log n). Each point update and prefix query is O(log n). The tree uses O(n) space.

Failure Example

Mixing zero-based public indexes with one-based internal indexes is the most common Fenwick bug. If the conversion index += 1 is forgotten, index 0 cannot move correctly through the tree.

Keep the conversion inside the data structure methods so callers use one consistent convention.

Common Confusions

A Fenwick tree is not a normal binary tree with node objects. It is stored in an array.

It is simpler than a segment tree for prefix-like operations, but less flexible for arbitrary range operations.

Another common mistake is mixing zero-based public indexes with one-based internal indexes. Keep the conversion in one place.

When To Use It

Use a Fenwick tree for point updates with prefix sums, range sums, frequency counts, inversion counting, and order-like queries based on cumulative counts.

Do not use it when the operation cannot be represented through prefix-style accumulation.

The Main Point

A Fenwick tree is a compact structure for prefix sums with point updates. Its public simplicity depends on careful index handling.