Fenwick Tree (Binary Indexed Tree)

Fenwick Tree (Binary Indexed Tree)

A plain prefix-sum array answers "sum of elements from index 1 to i" in $O(1)$, but updating a single element requires $O(n)$ time to recompute all subsequent prefix values. A Fenwick tree, also called a Binary Indexed Tree, or BIT, brings both operations down to $O(\log n)$ while using only $O(n)$ extra space and remarkably little code. It is the right tool whenever you need prefix sums on a mutable array and you don't require range-minimum or range-maximum (for those, reach for a segment tree instead).

The Key Insight: Lowest Set Bit

Every positive integer can be decomposed by its binary representation. The expression i & (-i) isolates the lowest set bit of i. For example:

• i = 6 (binary 110): 6 & -6 = 2 (binary 010)
• i = 4 (binary 100): 4 & -4 = 4 (binary 100)
• i = 7 (binary 111): 7 & -7 = 1 (binary 001)

A Fenwick tree uses this value to decide how much of the prefix each index "owns." Index i in the BIT array stores the sum of exactly i & (-i) consecutive elements ending at position i. Index 4 (binary 100, lowest bit = 4) is responsible for elements [1, 4]. Index 6 (binary 110, lowest bit = 2) covers [5, 6]. Index 7 (binary 111, lowest bit = 1) covers only [7, 7].

This encoding is what makes both operations fast: a prefix query decomposes into a chain of non-overlapping ranges by repeatedly stripping the lowest set bit, and an update propagates through the indices that "own" ranges containing the changed position by repeatedly adding the lowest set bit.

Querying a Prefix Sum

To find the sum of elements from 1 to i, start at i and collect tree[i], then jump to i - (i & -i), collect again, and repeat until i reaches zero. Each step removes one bit, so the loop runs at most $O(\log n)$ times.

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

    def query(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & (-i)
        return s

Updating a Position

To add delta to element i, start at i, add delta to tree[i], then jump to i + (i & -i) and repeat until i exceeds n. This visits every index whose responsible range includes position i.

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

Range Queries

A range sum [l, r] is simply the difference of two prefix queries: query(r) - query(l - 1). This is the same identity used for static prefix arrays, now available in $O(\log n)$ with updates.

    def range_query(self, l, r):
        return self.query(r) - self.query(l - 1)

Walked Example

Consider the array [2, 1, 5, 3, 4] (1-indexed). Initialize a BIT of size 5 and call update(i, arr[i]) for each position.

After all updates, tree[4] holds the sum of [1, 4] = 11, because index 4 (binary 100) owns four elements. To answer query(5):

• i=5: collect tree[5]=4, jump to 5 - (5&-5) = 5 - 1 = 4
• i=4: collect tree[4]=11, jump to 4 - (4&-4) = 4 - 4 = 0
• i=0: stop. Total = 4 + 11 = 15. Correct (2+1+5+3+4=15).

Now update index 3 by adding 2 (new value 7). Call update(3, 2):

• i=3: tree[3] += 2, jump to 3 + (3&-3) = 3 + 1 = 4
• i=4: tree[4] += 2, jump to 4 + (4&-4) = 4 + 4 = 8 > n, stop.

Only two nodes updated. Subsequent prefix queries will automatically reflect the change.

Applications

LeetCode 307. Range Sum Query - Mutable is the canonical Fenwick problem: build the BIT from the input, expose update(i, val - arr[i]) to overwrite a position, and answer sumRange(l, r) with query(r+1) - query(l) (after shifting to 1-indexed).

LeetCode 315. Count of Smaller Numbers After Self walks the array right to left, querying the BIT for the count of values already inserted that are strictly smaller than the current element, then inserting that element. With coordinate compression, this gives an $O(n \log n)$ solution to a problem that is $O(n^2)$ by brute force.

LeetCode 493. Reverse Pairs and the closely related problem of counting inversions, pairs $(i, j)$ where $i < j$ but arr[i] > arr[j], fall out of the same pattern. For inversions: process left to right, and for each element x, query the BIT for "how many elements already inserted are greater than x." With coordinate compression mapping values to $[1, n]$, this becomes query(n) - query(x) after inserting x via update(x, 1). The total across all elements is the inversion count, computed in $O(n \log n)$.

LeetCode 327. Count of Range Sum wants the number of prefix-sum pairs whose difference lies in $[lower, upper]$. Compute all prefix sums, coordinate-compress them, then for each prefix sum $P_j$ query the BIT for the count of prior $P_i$ in $[P_j - upper, P_j - lower]$ before inserting $P_j$.

LeetCode 1395. Count Number of Teams generalizes inversion counting to triples: for each middle element, count how many smaller elements are to its left and how many larger are to its right (and vice-versa). Two BIT sweeps deliver the answer in $O(n \log n)$.

2D Fenwick Tree

For sub-rectangle sum queries on a 2D grid with point updates, a 2D BIT extends naturally. The tree becomes a 2D array, and both update and query perform nested loops: the outer loop over rows uses the same i += i & (-i) / i -= i & (-i) logic, and the inner loop does the same for columns. Time per operation is $O(\log m \cdot \log n)$ for an $m \times n$ grid.

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):
        s = 0
        i = r
        while i > 0:
            j = c
            while j > 0:
                s += self.tree[i][j]
                j -= j & (-j)
            i -= i & (-i)
        return s

BIT vs. Segment Tree

For prefix-sum queries with point updates, a Fenwick tree is strictly simpler: it requires less code, has smaller constant factors, and uses exactly $n+1$ words of memory. A segment tree, by contrast, needs $4n$ space and more bookkeeping. The trade-off is generalization: segment trees support range-minimum, range-maximum, arbitrary associative operations, and lazy-propagation range updates. If you only need sum with point updates, reach for the BIT. If you need anything else, use the segment tree.

Complexity

Both update and query run in $O(\log n)$ time. Building the BIT by calling update $n$ times costs $O(n \log n)$; a smarter $O(n)$ construction exists but the simpler approach is almost always fast enough. Space is $O(n)$.

Recognizing this pattern

You're probably looking at a Fenwick tree when:

• The problem asks for a prefix sum on an array that also receives point updates.
• The merge operation is invertible (addition, XOR), so range = prefix(r) − prefix(l−1).
• You're counting inversions, smaller-to-the-left, or reverse pairs by sweeping values and querying prefixes.
• You're tempted to write a segment tree but it only ever does point updates and prefix queries.

Common templates:

• Point update + prefix sum: the textbook BIT. Example: Range Sum Query - Mutable.
• Inversion / reverse-pair counting: coordinate-compress, sweep right-to-left (or left-to-right), query prefix counts. Example: Count of Smaller Numbers After Self.
• Prefix XOR with point updates: same shape as sum, with XOR as the invertible op. Example: XOR Queries of a Subarray.
• Range update + point query via difference BIT: store deltas; point query becomes a prefix sum. Example: Corporate Flight Bookings.
• 2D BIT for grid sums with point updates: nested lowbit loops over rows and columns. Example: Range Sum Query 2D - Mutable.