Fenwick Tree (Binary Indexed Tree)

A segment tree is general but bulky — 4n memory and a dozen lines per operation. When all you need is prefix sums with point updates, the Fenwick tree (a.k.a. Binary Indexed Tree, BIT) does the same job in n memory and about three lines per operation. It’s the structure competitive programmers reach for first because it’s so short to type.

What it computes

A BIT supports, over an array of length n:

• update(i, delta) — add delta to arr[i], in O(log n).
• prefixSum(i) — the sum of arr[1..i], in O(log n).

And a range sum sum(i, j) is just prefixSum(j) − prefixSum(i − 1). That’s it — point update + prefix query, and everything else is built from those two.

The core idea: each index covers a power-of-two block

The magic is in how the tree array bit[] is laid out. bit[i] stores the sum of a block of arr ending at index i, whose length is the lowest set bit of i. That “lowest set bit” is computed by the famous trick:

lowbit(i) = i & (-i)

Because of two’s-complement, i & -i isolates the lowest 1-bit of i. For example lowbit(12) = lowbit(1100₂) = 100₂ = 4, so bit[12] covers arr[9..12] (4 elements). lowbit(6) = lowbit(110₂) = 10₂ = 2, so bit[6] covers arr[5..6].

The two loops

The beauty is that “walk the tree” is just repeatedly adding or subtracting lowbit:

• update(i, delta) — move up, hitting every block that contains i: start at i, add lowbit(i) each step until past n.
• prefixSum(i) — move down, accumulating disjoint blocks that tile [1..i]: start at i, subtract lowbit(i) each step until 0.

Both loops run at most log₂ n times because each step clears (or moves past) one bit.

class BIT {
    int n;
    vector<long long> bit;        // 1-indexed!
public:
    BIT(int n) : n(n), bit(n + 1, 0) {}
 
    void update(int i, long long delta) {     // add delta at index i
        for (; i <= n; i += i & (-i))
            bit[i] += delta;
    }
    long long prefixSum(int i) {               // sum of arr[1..i]
        long long s = 0;
        for (; i > 0; i -= i & (-i))
            s += bit[i];
        return s;
    }
    long long rangeSum(int i, int j) {         // sum of arr[i..j]
        return prefixSum(j) - prefixSum(i - 1);
    }
};

class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)      # 1-indexed
 
    def update(self, i, delta):        # add delta at index i
        while i <= self.n:
            self.bit[i] += delta
            i += i & (-i)              # move to the next block up
 
    def prefix_sum(self, i):           # sum of arr[1..i]
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & (-i)              # jump to the previous disjoint block
        return s
 
    def range_sum(self, i, j):
        return self.prefix_sum(j) - self.prefix_sum(i - 1)

class BIT {
    int n; long[] bit;                 // 1-indexed
    BIT(int n) { this.n = n; bit = new long[n + 1]; }
 
    void update(int i, long delta) {
        for (; i <= n; i += i & (-i))
            bit[i] += delta;
    }
    long prefixSum(int i) {
        long s = 0;
        for (; i > 0; i -= i & (-i))
            s += bit[i];
        return s;
    }
    long rangeSum(int i, int j) {
        return prefixSum(j) - prefixSum(i - 1);
    }
}

BIT vs segment tree — when to use which

The deciding factor: BIT only works for invertible aggregates (sum is invertible — you can subtract; min and max are not). If you need range min or max, you need a segment tree. If you need prefix sums, the BIT is shorter, smaller, and faster by a constant factor.

Range update, point query (the difference-array trick)

A BIT naturally does point update, range query. To flip it to range update, point query — “add v to all of [i, j], then read a single index” — store a difference array in the BIT: update(i, +v) and update(j + 1, −v). Then prefixSum(k) gives the total amount added at index k. Two BITs combined give range update + range query, but that’s rarely needed in interviews.

Quick check

Next: Basic Questions — warm-ups for both structures, then the practice set.