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).

Python Example

class FenwickTree:
    def __init__(self, size):
        self.tree = [0] * (size + 1)
 
    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.

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.

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.