Fenwick Tree (BIT): Prefix Sums on the Cheap

The Fenwick tree, also called the binary indexed tree or BIT, is the most compact data structure for prefix sum queries with point updates. Both operations run in O(log n) using a single array and a few lines of code. It is the segment tree’s smaller, faster cousin for the specific case of additive prefix sums.

The Idea

Each index i in the BIT array stores the sum of a specific block of the original array. The block’s length is determined by the lowest set bit of i. Index 4 in binary is 100, with lowbit 4, so BIT[4] stores the sum of the four elements ending at original index 4. Index 6 is 110, with lowbit 2, so BIT[6] stores the sum of the two elements ending at original index 6.

This odd-looking layout lets us compute any prefix sum by walking from i down to zero, repeatedly subtracting the lowest set bit. The number of bits in i bounds the number of steps, which gives O(log n).

The Lowbit Trick

In two’s complement representation, i and the bitwise AND of i with negative i isolate the lowest set bit. This single expression is the engine of the data structure.

def lowbit(i):
    return i & -i

For i equal to 12, binary 1100, lowbit returns 4. For i equal to 6, binary 110, lowbit returns 2. We use this to jump up the tree when updating and down the tree when querying.

Implementation

The BIT uses 1-based indexing for cleaner arithmetic. Index zero is unused.

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

    def update(self, i, delta):
        i += 1
        while i <= self.n:
            self.tree[i] += delta
            i += i & -i

    def prefix(self, i):
        i += 1
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def range_sum(self, l, r):
        return self.prefix(r) - (self.prefix(l - 1) if l else 0)

bit = Fenwick(6)
for i, x in enumerate([1, 3, 5, 7, 9, 11]):
    bit.update(i, x)
print(bit.prefix(3))
print(bit.range_sum(1, 4))
bit.update(2, 10)
print(bit.range_sum(1, 4))

The whole class is under 20 lines and handles arbitrary additive prefix sums with point updates.

Why the Layout Works

Think of i in binary. The lowest set bit of i isolates the size of the segment stored at BIT[i]. When you query prefix sum up to index i, you peel off segments one bit at a time, starting from the highest bit in i and ending at zero. Each step subtracts a power of two, so the number of steps equals the number of set bits in i, bounded by log n.

When you update index i, you climb upward through every node whose segment contains i. Adding the lowbit to i jumps to the next ancestor that contains the same position.

Range Updates with Difference Arrays

A vanilla BIT does point updates and prefix queries. To support range updates of the form “add a value v to every element in range l to r,” wrap the BIT around a difference array. Updating range l to r becomes two point updates: add v at index l and subtract v at index r plus one. A prefix sum at index i now gives the value at original index i rather than a sum.

To support both range updates and range queries, you need two BITs and a slightly more involved formula. This is a standard pattern in competitive programming.

Comparing With Segment Trees

A BIT is shorter, has smaller constant factors, and uses about half the memory of a segment tree. It only handles invertible aggregates like sum and XOR, because the prefix-difference trick relies on subtraction.

For min, max, or GCD, you cannot subtract one prefix from another to get a range, so plain BITs do not apply. In those cases, use a segment tree or a sparse table for static queries.

If you only need prefix sums and point updates, the BIT wins on simplicity and speed. If you need lazy propagation, range minimum, or arbitrary aggregates, reach for a segment tree instead.

2D Fenwick Tree

The data structure generalizes to multiple dimensions. A 2D BIT supports rectangular prefix sums and point updates on a grid in O(log n times log m). The implementation is two nested loops, each performing the standard lowbit walk.

class Fenwick2D:
    def __init__(self, rows, cols):
        self.r, self.c = rows, cols
        self.tree = [[0] * (cols + 1) for _ in range(rows + 1)]

    def update(self, x, y, delta):
        x += 1
        while x <= self.r:
            yy = y + 1
            while yy <= self.c:
                self.tree[x][yy] += delta
                yy += yy & -yy
            x += x & -x

    def prefix(self, x, y):
        x += 1
        s = 0
        while x > 0:
            yy = y + 1
            while yy > 0:
                s += self.tree[x][yy]
                yy -= yy & -yy
            x -= x & -x
        return s

This is enough for grid problems with hundreds of thousands of updates and queries.

Common Pitfalls

Off-by-one errors are the leading source of bugs. The BIT uses 1-based indexing internally, but most input arrays are 0-based. Pick one convention and stick with it consistently across update and query.

Forgetting that the BIT only supports invertible operations is the other common mistake. If you find yourself trying to track a maximum or a GCD, switch to a segment tree.

For complexity context on logarithmic data structures, see /blog/big-o-notation-explained and /blog/sorting-algorithms-overview.

Wrap up

The Fenwick tree gives you O(log n) prefix sums and point updates in about a dozen lines. It is the right choice whenever the problem is “prefix sum with point updates” and the aggregate is invertible. Anything more general belongs to its bigger sibling, the segment tree.