Fenwick Tree (Binary Indexed Tree) — Efficient Prefix Sums

Competitive programmers love Fenwick Trees because they solve a brutally common problem — range prefix-sum queries with point updates — in O(log n) time AND O(n) space, with constants so small the code fits in about 10 lines. You'll find them inside database engines for order-book aggregations, in game servers tracking cumulative scores, and in every serious competitive programming solution that involves frequency arrays or inversions. If you've ever hit a TLE on a naive cumulative-sum approach, a Fenwick Tree is likely the fix.

The core problem is this: you have an array of numbers that changes over time, and you need to repeatedly answer 'what is the sum of elements from index 1 to index k?' A flat prefix-sum array answers queries in O(1) but updates in O(n). A Fenwick Tree gives you O(log n) for both, with a constant factor that is almost embarrassingly small — often 3–5x faster in wall-clock time than a segment tree for the same problem.

By the end of this article you'll understand exactly why the bit-manipulation trick i += i & (-i) works, how to extend the tree for range updates and point queries, how to do a binary search on the tree itself, and the exact production bugs that bite engineers the first time they ship this structure in real code.

What is a Fenwick Tree? — Plain English

A Fenwick Tree (also called Binary Indexed Tree or BIT) is a data structure that answers the question 'what is the sum of elements from index 1 to i?' in O(log n) time, while also allowing you to update any element in O(log n) time. A naive array handles point updates in O(1) but prefix sums in O(n). A prefix sum array handles queries in O(1) but updates in O(n). A Fenwick tree strikes the middle — O(log n) for both. The trick is that each node in the BIT stores the sum of a specific range of elements, and the range size is determined by the lowest set bit of the node's index. For example, index 6 (binary 110) has lowest bit 2, so it stores the sum of 2 elements: arr[5]+arr[6].

How Fenwick Tree Works — Step by Step

Building and querying a BIT on arr=[1,3,5,7,9,11] (1-indexed, n=6):

Update(i, delta): add delta to BIT[i], then move to the next responsible node by adding the lowest set bit of i. 1. update(3, 5): BIT[3] += 5, then 3+(3&-3)=3+1=4 → BIT[4] += 5, then 4+4=8 > n, stop.

Query(i): sum from 1 to i by traversing upward removing the lowest set bit. 1. query(6): sum += BIT[6]; 6-(6&-6)=6-2=4 → sum += BIT[4]; 4-4=0 → stop. Sum = BIT[6]+BIT[4]. 2. BIT[6] covers arr[5]+arr[6]=9+11=20; BIT[4] covers arr[1]+arr[2]+arr[3]+arr[4]=1+3+5+7=16. Total=36.

Range query(l,r) = query(r) - query(l-1).

Worked Example — Tracing BIT Construction

Build BIT for arr=[1,3,5,7,9,11] (1-indexed).

Initialize BIT=[0,0,0,0,0,0,0] (index 0 unused).

update(1,1): BIT[1]+=1 → BIT[1]=1. 1+(1&-1)=1+1=2 → BIT[2]+=1 → BIT[2]=1. 2+2=4 → BIT[4]+=1=1. 4+4=8>6, stop. update(2,3): BIT[2]+=3=4. 2+2=4 → BIT[4]+=3=4. 8>6 stop. update(3,5): BIT[3]+=5=5. 3+1=4 → BIT[4]+=5=9. 8>6 stop. update(4,7): BIT[4]+=7=16. 4+4=8>6 stop. update(5,9): BIT[5]+=9=9. 5+1=6 → BIT[6]+=9=9. 6+2=8>6 stop. update(6,11): BIT[6]+=11=20. 6+2=8>6 stop.

Final BIT=[0,1,4,5,16,9,20]. query(6): BIT[6]=20; 6-2=4; BIT[4]=16; 4-4=0 stop. Sum=36. Correct (1+3+5+7+9+11=36).

Implementation

A BIT is implemented as a 1-indexed array. The update operation adds a delta to BIT[i] and propagates to parent nodes by adding the lowest set bit (i += i & -i). The query operation accumulates sums by stripping the lowest set bit (i -= i & -i) until i reaches 0. Construction can be done in O(n log n) via n updates, or O(n) by a smarter initialization. Point update with range query is the most common variant; range update with point query requires a difference BIT.

class FenwickTree:
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)  # 1-indexed

    def update(self, i, delta):
        """Add delta to position i (1-indexed)."""
        while i <= self.n:
            self.bit[i] += delta
            i += i & (-i)  # move to next responsible node

    def query(self, i):
        """Prefix sum from 1 to i (1-indexed)."""
        total = 0
        while i > 0:
            total += self.bit[i]
            i -= i & (-i)  # remove lowest set bit
        return total

    def range_query(self, l, r):
        """Sum from l to r (both 1-indexed)."""
        return self.query(r) - self.query(l - 1)

    def build(self, arr):
        """Build from 0-indexed array in O(n log n)."""
        for i, val in enumerate(arr):
            self.update(i + 1, val)

# Example
ft = FenwickTree(6)
ft.build([1, 3, 5, 7, 9, 11])
print(ft.query(6))        # 36 (sum of all)
print(ft.range_query(2,4)) # 15 (3+5+7)
ft.update(3, 2)            # arr[3] becomes 7
print(ft.range_query(2,4)) # 17 (3+7+7)

Frequently Asked Questions