Fenwick tree (binary indexed tree)

You’ll recognise it when

• An array changes one element at a time, and between changes you need sums of prefixes or ranges.
• Both kinds of operation come in large numbers, say 10⁵ each, so O(n) per operation is too slow.
• You count “how many earlier values are smaller than this one” while scanning: inversions, rank queries, smaller-after-self.
• The operation can be undone (sum, xor, count). Min and max can’t, which rules the Fenwick tree out for them.

It’s often confused with the segment tree. That does everything a Fenwick tree does and more (min, max, lazy range updates), at the cost of about four times the code. For sums, the Fenwick tree is the shorter tool.

The idea

Plain prefix sums answer any range sum in O(1), but one changed element shifts every prefix after it, and fixing them is O(n). Storing the raw array is the opposite: updates are free, sums are O(n). The Fenwick tree sits in between, with both at O(log n).

Think of money split across envelopes. Envelope 12 holds the takings of days 9 to 12, envelope 8 holds days 1 to 8, envelope 11 holds day 11 only. To total days 1 to 12 you open two envelopes, 12 and 8, not twelve. When day 3’s figure changes, you correct only the few envelopes whose span includes day 3: 3, 4 and 8.

Which envelope holds which days is decided by the binary form of its number. Take i, find its lowest set bit, call it lowbit(i). Then tree[i] holds the sum of the lowbit(i) elements ending at i, that is a[i − lowbit(i) + 1..i].

In code, lowbit(i) is i & -i. In two’s complement, -i is ~i + 1: flipping every bit turns the trailing zeros into ones, and the +1 carries through them back to zeros, stopping at the lowest set bit. So i and -i agree on that bit and on nothing above it. For 12 = 01100, -12 ends in …10100, and 12 & -12 = 00100 = 4.

How it works

The array is 1-indexed: position 0 has no set bit, so it would cover zero elements and the loops below would never move. Scroll through the steps and the graphic follows along; the bottom rows show each i in binary with its lowest set bit bright. You can also edit the array and the operations, or roll a random input.

Why it’s correct: clearing the lowest bit of i gives i − lowbit(i), which is exactly where tree[i]’s range starts (minus one), so the bars visited by a query sit side by side and tile [1, i] with no gaps or overlaps. For updates, adding the lowest bit of i lands on the smallest index above i whose bar is long enough to still reach back past i; every bar that contains position p lies on that chain, and no other bar does.

class Fenwick:
    """Point updates and prefix sums in O(log n). Positions are 1..n."""

    def __init__(self, values):
        self.n = len(values)
        # tree[i] holds a range sum; tree[0] is unused.
        self.tree = [0] * (self.n + 1)
        for i, x in enumerate(values, start=1):
            self.update(i, x)

    def update(self, i, delta):
        """a[i] += delta: fix every node whose range contains i."""
        while i <= self.n:
            self.tree[i] += delta
            i += i & -i

    def prefix_sum(self, i):
        """a[1] + a[2] + ... + a[i]."""
        total = 0
        while i > 0:
            total += self.tree[i]
            i -= i & -i
        return total

    def range_sum(self, l, r):
        """a[l] + ... + a[r]."""
        return self.prefix_sum(r) - self.prefix_sum(l - 1)

#include <vector>
using namespace std;

// Point updates and prefix sums in O(log n). Positions are 1..n.
struct Fenwick {
    int n;
    vector<long long> tree;                         // tree[0] is unused

    explicit Fenwick(const vector<long long>& values)
        : n(values.size()), tree(values.size() + 1, 0) {
        for (int i = 1; i <= n; i++) update(i, values[i - 1]);
    }

    // a[i] += delta: fix every node whose range contains i.
    void update(int i, long long delta) {
        while (i <= n) {
            tree[i] += delta;
            i += i & -i;
        }
    }

    // a[1] + a[2] + ... + a[i].
    long long prefixSum(int i) const {
        long long total = 0;
        while (i > 0) {
            total += tree[i];
            i -= i & -i;
        }
        return total;
    }

    // a[l] + ... + a[r].
    long long rangeSum(int l, int r) const {
        return prefixSum(r) - prefixSum(l - 1);
    }
};

// Point updates and prefix sums in O(log n). Positions are 1..n.
class Fenwick {
    private final int n;
    private final long[] tree;                      // tree[0] is unused

    Fenwick(long[] values) {
        n = values.length;
        tree = new long[n + 1];
        for (int i = 1; i <= n; i++) update(i, values[i - 1]);
    }

    // a[i] += delta: fix every node whose range contains i.
    void update(int i, long delta) {
        while (i <= n) {
            tree[i] += delta;
            i += i & -i;
        }
    }

    // a[1] + a[2] + ... + a[i].
    long prefixSum(int i) {
        long total = 0;
        while (i > 0) {
            total += tree[i];
            i -= i & -i;
        }
        return total;
    }

    // a[l] + ... + a[r].
    long rangeSum(int l, int r) {
        return prefixSum(r) - prefixSum(l - 1);
    }
}

Why it’s O(log n)

A query clears one set bit per step, and i has at most ⌊log₂ n⌋ + 1 set bits. An update adds the lowest bit, which makes the lowest set bit at least twice as big each step, so after at most log₂ n steps i passes n.

Building by calling update for every element is O(n log n). The structure is one array of n + 1 numbers, so space is O(n).

Common mistakes

fw.update(i, x)        # ✗ i from enumerate(a), starts at 0
fw.update(i + 1, x)    # ✓ positions 1..n

fw.prefix_sum(r) - fw.prefix_sum(l)       # ✗ drops a[l]
fw.prefix_sum(r) - fw.prefix_sum(l - 1)   # ✓

vector<int> tree;         // ✗ overflows silently
vector<long long> tree;   // ✓

Variations

• Range update, point query. Store the difference array instead: adding v to a[l..r] is update(l, v) and update(r + 1, −v), and a[i] is prefix_sum(i). Range update and range sum needs two trees.
• Counting inversions. Compress values to ranks 1..m, scan right to left, and for each value add prefix_sum(rank − 1) (how many smaller values sit to its right) before update(rank, 1). O(n log n) in total.
• 2-D Fenwick tree. Nest the loops: tree[x][y] over both coordinates gives rectangle sums on a grid with point updates in O(log n · log m).
• Linear build and binary lifting. Copy the array into tree, then for each i add tree[i] into tree[i + lowbit(i)]: O(n). And to find the first position where the prefix sum reaches k, walk down powers of two from the top instead of binary searching over prefix_sum: O(log n).
• Segment tree. When you need min, max or lazy range assignments, use a segment tree: it stores every range explicitly, so it doesn’t need to subtract.