02 — Fenwick Trees (Binary Indexed Trees)¶

Phase 5 | Week 31 | Mar 2 – Mar 8, 2027

A Fenwick tree (also called a Binary Indexed Tree, or BIT) answers the same category of problems as a segment tree — range sum queries with point updates — but with simpler code and a lower constant factor. The tradeoff: it handles fewer variants. If you need range minimum/maximum queries, or lazy range updates, you need a segment tree. If you need prefix sums with point updates, BIT is cleaner. Know both; use BIT when it fits.

The BIT Invariant¶

The core idea is non-obvious until you see it once, and then it’s obvious forever.

What tree[i] stores: The sum of elements from index i - lowbit(i) + 1 to index i, where lowbit(i) = i & (-i) (the lowest set bit of i in binary).

This is abstract. Here’s the concrete picture for n=8:

i       binary    lowbit(i)    tree[i] covers
     0001      1            arr[1..1]
     0010      2            arr[1..2]
     0011      1            arr[3..3]
     0100      4            arr[1..4]
     0101      1            arr[5..5]
     0110      2            arr[5..6]
     0111      1            arr[7..7]
     1000      8            arr[1..8]

Each tree[i] is responsible for a range whose length is the lowest set bit of i. This specific assignment ensures that:

A prefix query sum(1..i) can be answered by summing at most O(log n) nodes
A point update propagates to at most O(log n) nodes

Prefix Query: O(log n)¶

To compute sum(1..i), traverse from i to 1 by repeatedly removing the lowest set bit:

def prefix_sum(i, tree):
    total = 0
    while i > 0:
        total += tree[i]
        i -= i & (-i)    # remove lowest set bit: move to parent range
    return total

Example: prefix_sum(7) → nodes 7 (covers 7), 6 (covers 5-6), 4 (covers 1-4) → sum of arr[1..7].

Point Update: O(log n)¶

To update arr[i] += delta, traverse from i to n by repeatedly adding the lowest set bit:

def update(i, delta, tree, n):
    while i <= n:
        tree[i] += delta
        i += i & (-i)    # add lowest set bit: move to next responsible ancestor

Why the opposite direction? Query goes from i toward 0 (removing lowbit, shrinking toward the parent’s prefix). Update goes from i toward n (adding lowbit, propagating to all ranges that include i).

Range Query: O(log n)¶

Range sum from l to r:

def range_sum(l, r, tree):
    return prefix_sum(r, tree) - prefix_sum(l - 1, tree)

Classic prefix difference trick. No special code needed.

Point Update + Prefix Query: Full Implementation¶

class BIT:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)   # 1-indexed

    def update(self, i, delta):
        while i <= self.n:
            self.tree[i] += delta
            i += i & (-i)

    def query(self, i):              # prefix sum [1..i]
        total = 0
        while i > 0:
            total += self.tree[i]
            i -= i & (-i)
        return total

    def range_query(self, l, r):     # sum [l..r]
        return self.query(r) - self.query(l - 1)

Build from an existing array: call update(i, arr[i]) for each i. This is O(n log n). A smarter O(n) construction exists (compute tree[i] directly), but the update-based construction is sufficient for most use cases.

Order Statistics with BIT¶

One powerful BIT application: counting inversions and finding the kth smallest element dynamically.

Counting inversions: For each element, count how many previous elements are greater. Compress values to [1, n], then for each element x:

Query prefix_sum(x - 1) = number of previous elements ≤ x - 1 = elements that DON’T form an inversion with x
Inversions formed by x = (number of elements seen so far) - prefix_sum(x - 1)
Update BIT at position x

Total inversions = sum over all elements. O(n log n).

Finding kth smallest dynamically: Maintain a BIT where tree[v] = 1 if value v is present, 0 otherwise. To find kth smallest, binary search on the prefix sum: find the smallest i such that prefix_sum(i) ≥ k. Can be done in O(log² n) with repeated halving, or O(log n) with the “walking down the BIT” technique.

2D Fenwick Tree¶

For 2D range sum queries: “sum of elements in rectangle (r1, c1) to (r2, c2) with point updates.”

Structure: A 2D BIT where each node stores a BIT.

class BIT2D:
    def __init__(self, m, n):
        self.m, self.n = m, n
        self.tree = [[0] * (n + 1) for _ in range(m + 1)]

    def update(self, r, c, delta):
        i = r
        while i <= self.m:
            j = c
            while j <= self.n:
                self.tree[i][j] += delta
                j += j & (-j)
            i += i & (-i)

    def query(self, r, c):        # sum [1..r][1..c]
        total = 0
        i = r
        while i > 0:
            j = c
            while j > 0:
                total += self.tree[i][j]
                j -= j & (-j)
            i -= i & (-i)
        return total

    def range_query(self, r1, c1, r2, c2):
        return (self.query(r2, c2)
                - self.query(r1-1, c2)
                - self.query(r2, c1-1)
                + self.query(r1-1, c1-1))

O(log m × log n) per operation. Clean and fast.

BIT vs. Segment Tree: When to Use Which¶

Need	Use
Point update + range sum	Either. BIT is simpler.
Range update + point query	BIT with difference array trick
Range update + range query	Segment tree with lazy propagation
Range min/max query	Segment tree only
2D range queries	2D BIT (simpler) or 2D segment tree
Counting inversions	BIT (the natural fit)
Order statistics (kth element)	BIT with binary lifting

BIT strength: ~3x less code than segment tree. Lower constant factor. 2D BIT is simpler than 2D segment tree.

Segment tree strength: Handles all aggregates (min, max, gcd, etc.) and lazy range updates. BIT cannot do lazy range updates in the standard form.

What Most Engineers Get Wrong¶

1-indexing is mandatory for BIT. The i & (-i) operation gives 0 when i = 0, causing an infinite loop if you use 0-indexed. Always allocate n+1 space and use 1-indexed positions. Convert your input array from 0-indexed to 1-indexed when calling update/query.

Range update with BIT: Many people don’t know that BIT can support range updates via a difference array technique. To add val to all elements in [l, r]: update position l by +val, update position r+1 by -val. The prefix sum at any point i then gives the value at arr[i] after all range updates. This handles range-add + point-query but NOT range-add + range-query (which needs segment tree).

Practice Problems¶

Medium¶

Range Sum Query - Mutable — LeetCode 307. Solve with BIT. Compare your BIT solution with your segment tree solution from the previous file — same problem, different tools.
Count of Smaller Numbers After Self — LeetCode 315. Classic inversion counting via BIT with coordinate compression.

Hard¶

Reverse Pairs — LeetCode 493. Extended inversion counting. BIT with modified query condition.
Count of Range Sum — LeetCode 327. Merge sort or BIT with coordinate compression. Hard in both approaches.