Fenwick Tree (Binary Indexed Tree)

A Fenwick tree (or Binary Indexed Tree) is a compact array that answers two questions in O(log n): "add delta to position i" and "what is the prefix sum of positions 1..i?". It beats a plain prefix-sum array, which is O(1) to query but O(n) to update, and a plain array, which is O(1) to update but O(n) to sum. The whole structure runs on one bit trick: i & -i, which isolates the lowest set bit of i.

For a size-7 tree holding [_, 1, 3, 1, 9, 1, 5, 2], the responsible blocks are: tree[1] covers index 1, tree[2] covers 1..2, tree[4] covers 1..4, and so on — exactly the ranges the low bit encodes.

Intuition

Write any index in binary. The value i & -i is the lowest set bit — the size of the range tree[i] is responsible for. Index 6 is 110, so its low bit is 2: tree[6] covers two elements (positions 5 and 6). Index 4 is 100, low bit 4: tree[4] covers four (positions 1..4).

That single fact powers both operations. When you update position i, every slot whose block contains i must change — and those slots are found by repeatedly adding the low bit, walking up a short chain of ancestors. When you query the prefix 1..i, you stitch together a few disjoint blocks: take tree[i], jump back past the block it just covered by subtracting the low bit, and repeat until you hit 0.

Walk through it

Step through the animation on the right. The top row is the BIT array, 1-indexed; the i pointer walks the index.

First we run update(3, +2). At i = 3 (011, low bit 1) we add 2 to tree[3], then climb i += i & -i = 3 + 1 = 4. At i = 4 (100, low bit 4) we add 2 to tree[4], then climb to 4 + 4 = 8, which is past n = 7, so we stop. Two slots touched.

Then we run query(5) — the prefix sum of positions 1..5. Starting with total = 0 at i = 5 (101), we add tree[5] then descend i = 5 - 1 = 4. At i = 4 (100) we add tree[4] then descend 4 - 4 = 0, stopping. The answer is tree[5] + tree[4] — two blocks (position 5, plus positions 1..4) that exactly tile 1..5.

The code, line by line

class Fenwick:
    def __init__(self, n):
        self.tree = [0] * (n + 1)   # 1-indexed
 
    def update(self, i, delta):
        while i < len(self.tree):
            self.tree[i] += delta
            i += i & (-i)           # climb to next responsible slot
 
    def query(self, i):             # prefix sum of [1..i]
        total = 0
        while i > 0:
            total += self.tree[i]
            i -= i & (-i)           # descend to previous block
        return total

• The array is 1-indexed with one extra slot, so i = 0 is the natural terminator for the query loop.
• i & (-i) isolates the lowest set bit. In two's complement, -i flips all bits and adds one, leaving only the lowest set bit shared with i.
• update climbs: i += i & (-i) jumps to the next larger slot whose block covers i. The loop ends once i runs past the array, so it touches at most one slot per bit — O(log n).
• query descends: after adding tree[i], i -= i & (-i) removes the block just counted and lands on the end of the previous, disjoint block. Stop at 0.
• Building from an array is just n calls to update, giving O(n log n) — or O(n) with an in-place trick.

Complexity

Both operations follow a chain bounded by the number of bits in i, so each is O(log n). The structure itself is a single array of n + 1 integers — far lighter than a segment tree, which needs about 2n to 4n nodes.

When to use / pitfalls

Practice