Fenwick (binary indexed) trees

What this chapter covers

The segment tree solved "range query plus update" for any aggregate, at the cost of a real tree of nodes. But the most common version of that problem — prefix sums with point updates — has a far leaner solution. The Fenwick tree, or binary indexed tree, does the same O(log n) query and update using nothing but one array and the binary representation of the indices: no nodes, no pointers, two-line loops. It's one of those rare structures that feels like a magic trick the first time you see it work, and its whole secret is that each index is responsible for a range whose length is its lowest set bit. This chapter builds it, watches the index jumps that i & -i produces, and shows it beating both the array baselines and the segment tree for sums.

A bit of history

The Fenwick tree is young and has a precise origin: Peter Fenwick published it in 1994, in a paper titled "A New Data Structure for Cumulative Frequency Tables." He wasn't chasing an abstract problem — he needed fast cumulative frequencies for arithmetic coding, a compression technique where you must repeatedly ask "how many symbols so far are less than this one?" and update counts as you go. That's prefix-sum-with-updates exactly. Fenwick's insight was that the binary structure of the indices already encodes a tree, so you don't need to build one: index i can implicitly stand for a range, and the transitions between these ranges are just adding or removing the lowest set bit. The result was so much simpler than a segment tree for this case that it spread rapidly through competitive programming, where "binary indexed tree" or "BIT" is now standard vocabulary. It's the rare data structure named after its inventor that arrived essentially in final form.

The intuition

Number the array positions 1 through n (Fenwick trees are 1-indexed — that's not a quirk, it's load-bearing). Now here's the trick: index i is responsible for storing the sum of a range of the array ending at i, and the length of that range is i & -i, the value of i's lowest set bit. Index 6 is 110 in binary, lowest set bit 2, so it covers the 2 positions ending at 6 (that is, 5 and 6). Index 8 is 1000, lowest set bit 8, so it covers all 8 positions 1 through 8. Index 3 is 011, lowest set bit 1, so it covers just position 3. Remarkably, these ranges tile the array perfectly at every scale.

Because they tile, a prefix sum is a walk down the indices. To sum positions 1 through 6, start at 6: add its stored range (positions 5–6), then jump to 6 − (6 & -6) = 4, which covers positions 1–4; add that; jump to 4 − 4 = 0 and stop. Two nodes, and their ranges 5–6 and 1–4 tile 1–6 exactly. An update is the mirror — a walk up. To add to position 3, you must fix every stored range that includes position 3: index 3 (covers 3), then 3 + (3 & -3) = 4 (covers 1–4), then 4 + 4 = 8 (covers 1–8), then 8 + 8 = 16, past the end, stop. Each jump strips or adds the lowest set bit, and since a number has at most log n bits, each walk is O(log n). No tree is ever built; the tree lives in the arithmetic.

Complexity: how it scales

Build is $O(n)$, prefix query and point update are both $O(\log n)$ — one jump per bit of the index. A range sum is two prefix sums subtracted, still $O(\log n)$, and that subtraction is exactly why the Fenwick tree needs an invertible operation: to get the sum of [lo, hi] as prefix(hi) − prefix(lo−1), you must be able to "subtract off" the part you don't want, which works for sums but not for min or max. Space is $O(n)$ — a single array, no per-node overhead. The chart runs the same mixed query/update workload as the segment-tree chapter:

At 40000 elements the Fenwick tree ran the mixed workload in about 6 ms, against the raw array's 278 ms (46× slower) and prefix sums' 2433 ms (403× slower) — the same O(log n)-beats- O(n) story as the segment tree. But compare it to the segment tree itself: that chapter's segment tree took 25 ms on the equivalent workload, so the Fenwick tree is roughly four times faster for sums, with a tiny fraction of the code and half the memory. That's the payoff of a structure specialized to exactly one job.

What it's good at, what it isn't

The Fenwick tree is the right tool the instant your problem is prefix (or range) sums with point updates. It's tiny — a couple of loops and one array — so it's fast, cache-friendly, and almost impossible to get wrong once you know the i & -i idiom. For cumulative frequencies, running totals over mutable data, counting inversions, and the countless "range sum with updates" problems in competitive programming, it's the default, beating the segment tree on constant factors and beating the array approaches on complexity.

Its limits come from that same specialization. It only handles invertible aggregates — sums, xors, products (if nonzero) — because range queries subtract prefixes; for min, max, or gcd, where you can't subtract, you need a segment tree. It answers prefix-anchored queries naturally; arbitrary structural queries want the segment tree's explicit ranges. And its 1-indexing and bit-twiddling, while short, are famously error-prone until they click. The Fenwick tree is the specialist: unbeatable in its narrow lane, inapplicable outside it.

The data, or the inputs

The face-off runs 5000 mixed prefix-query and update operations at growing sizes — the same workload as the segment-tree chapter, so the two structures are directly comparable. The animation traces one prefix-sum query and one update over an eight-element tree, so you can watch the i & -i jumps walk down and up the indices.

Build it, one function at a time

The prefix sum walks down, subtracting the lowest set bit:

def prefix_sum(self, i, probe=None):
    """Sum of elements 1..i in O(log n). Walk DOWN: add tree[i], then jump to
    i - (i & -i) — removing the lowest set bit — until i reaches 0. Each node covers a
    range of length equal to its lowest set bit, and those ranges tile [1..i] exactly,
    so their stored sums add up to the prefix."""
    total = 0
    while i > 0:
        total += self._tree[i]
        if probe is not None:
            probe.append(i)
        i -= i & -i
    return total

The update walks up, adding it:

def update(self, i, delta, probe=None):
    """Add `delta` to element i (1-indexed) in O(log n). Walk UP: after touching index
    i, jump to i + (i & -i) — adding the lowest set bit — which is the next node whose
    range covers position i. Each jump clears toward the high bits, so at most log n
    steps reach past the end."""
    while i <= self._n:
        self._tree[i] += delta
        if probe is not None:
            probe.append(i)
        i += i & -i

And a range sum is the difference of two prefixes — the step that requires an invertible aggregate:

def range_sum(self, lo, hi):
    """Sum of [lo..hi] by subtracting prefixes — the trick that needs an INVERTIBLE
    aggregate (why Fenwick trees do sums, not min/max)."""
    return self.prefix_sum(hi) - self.prefix_sum(lo - 1)

Watch it work

Here's the index arithmetic in motion over eight positions. First a prefix_sum(6): orange marks the current index, blue the indices already added. Watch it start at 6, add that node's range, and jump to 4 by subtracting the lowest set bit (6 − 2 = 4), then to 0 — two nodes whose ranges tile 1 through 6. Then an update to position 3: it walks the other way, 3 → 4 → 8, adding the lowest set bit each time to hit every node whose range covers position 3. The captions show the binary of each index so you can see the lowest-set-bit jump directly. No tree is drawn because there is no tree — just an array and these jumps:

The complete code

Both versions in one place — flip between them. The from-scratch tab is the Fenwick tree — note how little there is. The library tab is the two array baselines it beats (raw array and prefix sums), because there's no Fenwick tree in the standard library; the whole point is that this structure is small enough to type from memory.

"""The Fenwick tree — also called a binary indexed tree, or BIT — the lean specialist for
prefix sums with updates. It does the same O(log n) prefix-query and point-update job as a
segment tree, for the special case of an invertible aggregate like sum, in a fraction of
the code and memory: one array and a two-line loop each way.

Its whole cleverness is in the indices. Node i is "responsible" for a range of the array
whose length is the lowest set bit of i — the value `i & -i`. Those ranges tile the array
perfectly, so a prefix sum walks *down* the indices by repeatedly subtracting the lowest
set bit, and an update walks *up* by adding it. No tree of nodes and pointers — just
arithmetic on the binary representation of the index.
"""


class FenwickTree:
    def __init__(self, n):
        self._n = n
        self._tree = [0] * (n + 1)          # 1-indexed; index 0 is unused

    @classmethod
    def from_data(cls, data):
        """O(n) build: copy the values in, then let each index push its running total up
        to the parent that covers it. Faster than n separate updates."""
        ft = cls(len(data))
        ft._tree = [0] + list(data)
        for i in range(1, ft._n + 1):
            j = i + (i & -i)
            if j <= ft._n:
                ft._tree[j] += ft._tree[i]
        return ft

    # region: update
    def update(self, i, delta, probe=None):
        """Add `delta` to element i (1-indexed) in O(log n). Walk UP: after touching index
        i, jump to i + (i & -i) — adding the lowest set bit — which is the next node whose
        range covers position i. Each jump clears toward the high bits, so at most log n
        steps reach past the end."""
        while i <= self._n:
            self._tree[i] += delta
            if probe is not None:
                probe.append(i)
            i += i & -i
    # endregion

    # region: prefix_sum
    def prefix_sum(self, i, probe=None):
        """Sum of elements 1..i in O(log n). Walk DOWN: add tree[i], then jump to
        i - (i & -i) — removing the lowest set bit — until i reaches 0. Each node covers a
        range of length equal to its lowest set bit, and those ranges tile [1..i] exactly,
        so their stored sums add up to the prefix."""
        total = 0
        while i > 0:
            total += self._tree[i]
            if probe is not None:
                probe.append(i)
            i -= i & -i
        return total
    # endregion

    # region: range_sum
    def range_sum(self, lo, hi):
        """Sum of [lo..hi] by subtracting prefixes — the trick that needs an INVERTIBLE
        aggregate (why Fenwick trees do sums, not min/max)."""
        return self.prefix_sum(hi) - self.prefix_sum(lo - 1)
    # endregion

"""No Fenwick tree in the standard library — it's a build-it-yourself structure. The
baselines are the same two array approaches from the segment-tree chapter, each fast at one
operation and O(n) at the other:

  - a RAW array: O(1) update, O(n) prefix query;
  - a PREFIX-SUM array: O(1) query, O(n) update (rebuild).

The Fenwick tree matches a segment tree's O(log n) for BOTH — on sums specifically — with far
less code, which is the point of the face-off.
"""


# region: raw_array
class RawArray:
    """Raw values: update is trivial, prefix sum re-adds the slice — O(n)."""

    def __init__(self, data):
        self._d = list(data)

    def prefix_sum(self, i):
        return sum(self._d[:i])                 # O(n)

    def update(self, i, delta):
        self._d[i] += delta                     # O(1)
# endregion


# region: prefix_sums
class PrefixSums:
    """Precomputed prefix sums: O(1) query, but any update forces an O(n) rebuild."""

    def __init__(self, data):
        self._d = list(data)
        self._rebuild()

    def _rebuild(self):
        self._p = [0]
        for x in self._d:
            self._p.append(self._p[-1] + x)

    def prefix_sum(self, i):
        return self._p[i]                       # O(1)

    def update(self, i, delta):
        self._d[i] += delta
        self._rebuild()                         # O(n)
# endregion

Scratch vs library

The array-baseline comparison tells the same story as the segment tree — O(log n) crushes O(n) on a mixed workload, 46× and 403× here. But the number that defines this chapter is the one you have to hold across two chapters: 6 ms for the Fenwick tree versus 25 ms for the segment tree on the equivalent workload. Same asymptotic class, same problem, but the Fenwick tree's tiny constant — one array, two-line loops, no node objects, cache-friendly — makes it four times faster in practice. This is the constant-factor lesson turned into a design principle: when a general structure and a specialized one have the same Big-O, the specialist usually wins on the constant, so match the tool to the exact problem. The segment tree is the right answer for min/max or range updates; for prefix sums, the Fenwick tree is smaller, faster, and harder to get wrong.

Where you'll actually meet it

Fenwick trees run wherever cumulative counts change. Arithmetic and range coders — Fenwick's original application — use them for adaptive symbol frequencies. Databases and analytics engines use them for running aggregates over mutable data. They're the standard tool for counting inversions (how far a sequence is from sorted) and for order-statistics-with-updates. And in competitive programming they're ubiquitous — "BIT" is reached for reflexively whenever a problem says "prefix sum" and "update" in the same breath. Any time you need a running total over data that keeps changing, the Fenwick tree is the lightest structure that does it in O(log n).

Takeaways

A Fenwick tree stores prefix-sum information implicitly in the binary structure of its indices: index i covers the i & -i positions ending at i, those ranges tile the array, and queries walk down subtracting the lowest set bit while updates walk up adding it — both $O(\log n)$, in one array and two short loops. It's the specialized, lean alternative to a segment tree for invertible aggregates, four times faster in this chapter's test and a tenth the code, at the cost of only doing sums, not min or max.

That completes the range-query trees, and nearly the whole tree tier. Two structures remain, and both step outside the binary-tree world. The next chapter, the B-tree, is the balanced tree reimagined for disk: instead of two children per node it has hundreds, because when each node is a disk block, minimizing the number of blocks you read matters more than anything — which is why B-trees, not red-black trees, index every database and filesystem on earth.