Fenwick Tree (Binary Indexed Tree)

The problem

You keep an array of numbers, such as daily sales, and you need two operations again and again:

• prefix sum: A[1] + A[2] + … + A[i]
• update: change one A[i]

A plain array makes updates O(1) but sums O(n). A prefix-sum array makes sums O(1) but updates O(n). With millions of both operations, either is too slow. A Fenwick tree (also called a binary indexed tree, BIT) does both in O(log n) with a single extra array and just a few lines of code.

The trick: ranges sized by the lowest 1 bit

Index from 1. Cell T[i] stores the sum of the lowbit(i) elements that end at position i, where lowbit(i) = the value of the lowest 1 bit of i, computed as i & -i:

i	binary	lowbit	T[i] covers
1	0001	1	A[1]
2	0010	2	A[1 … 2]
3	0011	1	A[3]
4	0100	4	A[1 … 4]
5	0101	1	A[5]
6	0110	2	A[5 … 6]
7	0111	1	A[7]
8	1000	8	A[1 … 8]

In the 3D model, each bar is one T[i], drawn over exactly the elements it covers.

Prefix sum: drop the lowest bit

To sum A[1 … i], add T[i], then jump to i − lowbit(i), and repeat until i = 0. The ranges fit together with no gaps and no overlaps.

prefix(7) with A = [3, 2, −1, 6, 5, 4, −3, 3]:

• i = 7 (0111): add T[7] = −3, so i becomes 6
• i = 6 (0110): add T[6] = A[5] + A[6] = 9, so i becomes 4
• i = 4 (0100): add T[4] = A[1] + … + A[4] = 10, so i becomes 0

Sum = −3 + 9 + 10 = 16. That took three steps, one per 1 bit in 0111.

Update: add the lowest bit

When A[i] changes by delta, every cell whose range contains i must change too. Those are exactly i, i + lowbit(i), and so on, until you pass n. Updating A[3] visits T[3], T[4] and T[8].

Range sums

sum(l … r) = prefix(r) − prefix(l − 1). For example sum(3 … 6) = prefix(6) − prefix(2) = 19 − 5 = 14.

Code

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

    def update(self, i, delta):
        while i <= self.n:
            self.t[i] += delta
            i += i & -i                        # next cell that covers i

    def prefix(self, i):
        s = 0
        while i > 0:
            s += self.t[i]
            i -= i & -i                        # drop the lowest 1 bit
        return s

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

A = [3, 2, -1, 6, 5, 4, -3, 3]
fw = Fenwick(len(A))
for i, x in enumerate(A, start=1):
    fw.update(i, x)
print(fw.prefix(7), fw.range_sum(3, 6))        # 16 14
fw.update(3, 5)                                # A[3] += 5
print(fw.prefix(7))                            # 21

#include <iostream>
#include <vector>
using namespace std;

struct Fenwick {
    int n; vector<long long> t;
    Fenwick(int n) : n(n), t(n + 1, 0) {}
    void update(int i, long long d) { for (; i <= n; i += i & -i) t[i] += d; }
    long long prefix(int i) { long long s = 0; for (; i > 0; i -= i & -i) s += t[i]; return s; }
};

int main() {
    vector<int> a = {3, 2, -1, 6, 5, 4, -3, 3};
    Fenwick fw(a.size());
    for (int i = 0; i < (int)a.size(); i++) fw.update(i + 1, a[i]);
    cout << fw.prefix(7) << " " << fw.prefix(6) - fw.prefix(2);   // 16 14
}

Fenwick tree vs segment tree

	Fenwick tree	Segment tree
Memory	n + 1 numbers	about 4n nodes
Code	~10 lines	~40 lines
Prefix / range sum	O(log n)	O(log n)
Range min / max	❌ not directly	✅
Range updates	with a second tree	with lazy propagation

Use a Fenwick tree when you need sums (or other invertible operations like XOR) and want short, fast code. Use a segment tree for min/max queries or more complex range operations.

Where is it used?

• Counting inversions in an array in O(n log n).
• Leaderboards and order statistics: how many scores are below x?
• Frequency tables that change over time, such as arithmetic coding in data compression, where Fenwick trees were first proposed (1994).
• Competitive programming, where its short code is a big advantage.

Common mistakes

• Using 0-based indices. The loop i -= i & -i never ends at 0, and i & -i of 0 is 0. Fenwick trees are 1-indexed.
• Storing the array itself in T. T[i] holds range sums, not A[i].
• Updating with the new value instead of the difference (delta = new − old).
• Building it by calling update n times and calling that O(n). It is O(n log n), unless you use the linear build.