Fenwick Tree (BIT)Fenwick trees

01Why it exists

Reach for it when you see:Prefix sums over data that keeps changing, inversions, how many are smaller than me, live rankings, wanting something lighter than a segment tree.

02The core idea

A Fenwick tree keeps an array tree the same length as the original, where each cell is responsible for a stretch of the array whose length is set by the lowest set bit of its index: lowbit(i) = i & −i. tree[6] (110₂) covers 2 elements, a[5..6]; tree[8] (1000₂) covers 8 elements, a[1..8]; an odd index covers only itself. The elegance of this split is that any prefix [1, i] breaks into O(log n) of those stretches, and any single position is covered by only O(log n) cells.

Prefix sum: start at i, add tree[i], then i −= lowbit(i), which strips the lowest set bit and jumps to the previous stretch. Each jump removes one 1 bit, so there are at most log n of them. Point update: start at i, add delta to tree[i], then i += lowbit(i) to jump to the next cell that is also responsible for i, until you run past n. Again at most log n jumps.

The two operations look almost identical; one subtracts the lowbit and the other adds it. Seeing why subtracting the lowbit lands exactly on the previous stretch takes a look at the binary, and the demo draws out the stretch each cell covers, so following a few jumps is enough to get the feel of it.

Compared with a segment tree: a Fenwick tree can only answer prefix-shaped queries — sums, XOR, counts, anything you can subtract back out — and a range maximum is beyond it, because maximum has no inverse operation. But whenever the problem is a prefix sum, it is shorter, faster and lighter on memory. The relationship between the two is the one between a specialised tool and a general-purpose one.

03The algorithm

1. 1Index from 1 (the lowbit of 0 is 0, which loops forever). Allocate tree = [0] * (n + 1).
2. 2update(i, delta): while i ≤ n: tree[i] += delta; i += i & −i.
3. 3prefix(i): s = 0; while i > 0: s += tree[i]; i −= i & −i.
4. 4The range sum over [l, r] is prefix(r) − prefix(l − 1).
5. 5When the value range is huge, compress the coordinates first (map each value to its rank in 1..m) and index by rank. Inversion counting and live rankings both work this way.

04Interactive demo

The bars along the top show the interval each tree[i] is responsible for. Computing prefix(6), watch i jump from 6 to 4 and then to 0; for update(3), watch it jump from 3 to 4 and then to 8. Every step shows the binary form and the lowbit.

05Code

The whole implementation is two loops, plus the O(n) build and the classic inversion-counting application. Pay attention to the coordinate-compression step.

class Fenwick:
    """Fenwick tree (binary indexed tree): prefix sums plus point updates, indexed from 1."""

    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)

    def update(self, i, delta):
        """a[i] += delta. Jump upward to every cell that is also responsible for i"""
        while i <= self.n:
            self.tree[i] += delta
            i += i & -i                    # add the lowbit

    def prefix(self, i):
        """a[1] + ... + a[i]. Jump downward, stitching the covered segments together"""
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i                    # strip the lowbit
        return s

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

    @classmethod
    def from_list(cls, a):
        """O(n) build: every cell adds itself into the cell above that is responsible for it"""
        f = cls(len(a))
        for i, x in enumerate(a, start=1):
            f.tree[i] += x
            j = i + (i & -i)
            if j <= f.n:
                f.tree[j] += f.tree[i]
        return f


f = Fenwick.from_list([5, 3, 8, 6, 2, 7, 4, 1])
print(f.prefix(6))          # 31
f.update(3, 2)
print(f.range_sum(2, 5))    # 3 + 10 + 6 + 2 = 21


# Classic application: inversions, or how many numbers to the right of me are smaller
def count_smaller_to_right(nums):
    ranks = {v: i + 1 for i, v in enumerate(sorted(set(nums)))}   # compress the values into 1..m
    f = Fenwick(len(ranks))
    out = []
    for v in reversed(nums):                # scan from right to left
        out.append(f.prefix(ranks[v] - 1))  # how many already seen are smaller than v
        f.update(ranks[v], 1)
    return out[::-1]

06Practice

• LeetCode 307Range Sum Query - Mutable (do it again with a Fenwick tree)Medium
• LeetCode 315Count of Smaller Numbers After SelfHard
• LeetCode 493Reverse PairsHard
• LeetCode 1409Queries on a Permutation With KeyMedium
• LeetCode 2179Count Good Triplets in an ArrayHard