Fenwick Tree (Binary Indexed Tree): Complete Guide with Python, Diagrams & Interview Questions

If you have an array of numbers and need to frequently calculate the sum of the first $K$ elements, a simple Prefix Sum data structure is great—until you need to update one of the values.

If you update a value in a standard prefix sum array, you have to recalculate the sums for the rest of the array, taking $O(N)$ time. In coding interviews (and real-time systems like stock tickers or game leaderboards), $O(N)$ updates are too slow.

Enter the Fenwick Tree, also known as a Binary Indexed Tree (BIT). It is an elegant, highly optimized data structure that achieves $O(\log N)$ time complexity for both point updates and range sum queries.

When Should You Use a Fenwick Tree?

A Fenwick Tree is the ideal choice when: * You need frequent point updates. * You need prefix sum or range sum queries. * The array size is large (up to $10^5$ – $10^6$). * You need an implementation simpler than a Segment Tree.

Common applications include: * Live scoreboards and game leaderboards * Stock price updates * Frequency arrays * Order statistics * Counting inversions in an array * Offline queries and coordinate compression

The Coordinate Compression Connection Fenwick Trees are frequently combined with coordinate compression in competitive programming and advanced interview questions when values are very large (for example, up to $10^9$). Since a BIT requires an array of size $N$, you cannot create an array of size $10^9$. Instead, you sort the unique values and map them down to the range [1...N] before feeding them into the BIT.

The Magic Intuition: The Least Significant Bit (LSB)

Before understanding the tree, you must understand the Least Significant Bit (LSB).

Take the number 12. In binary, 12 is 1100. Its LSB is 0100 (which is 4 in decimal). How do we find the LSB mathematically? Using bitwise operations: LSB(x) = x & -x.

Why does x & -x work?

Rather than thinking about the decimal value of ~x, remember that computers store negative numbers using two's complement. The expression x & -x always isolates the rightmost set bit of x.

 12 = 00001100
-12 = 11110100

00001100  (12)
11110100  (-12)
--------
00000100  (4)  -> The rightmost set bit is isolated!

Why is it called a tree? A Fenwick Tree is actually stored in a single flat array. The "tree" exists only conceptually because every index has a parent determined by adding or subtracting its LSB.

The Responsibility Formula

The most important property of a BIT is that tree[i] stores the sum of a specific range of elements:

tree[i] stores the sum of elements in the range [i - LSB(i) + 1, i]

Examples: * tree[6]: LSB(6) = 2. Stores range [6 - 2 + 1, 6] = [5, 6] * tree[12]: LSB(12) = 4. Stores range [12 - 4 + 1, 12] = [9, 12]

The Responsibility Table

Visualizing the BIT Array

If our original array is [3, 2, -1, 6, 5, 4, 7, 8], our BIT array looks like this:

Index:   1  2  3  4  5  6  7  8
BIT:     3  5 -1 10  5  9  7 34

(Note: tree[8] stores the sum of indices 1 through 8, which is 34).

If we need to Update index 5, we must update all nodes responsible for index 5. We do this by moving UP the tree (adding the LSB):

graph TD
    A["tree[5]"] -->|"5 + LSB(1) = 6"| B["tree[6]"]
    B -->|"6 + LSB(2) = 8"| C["tree[8]"]
    C -->|"8 + LSB(8) = 16"| D["Out of Bounds: Stop"]

    style A fill:#bbf,stroke:#333
    style B fill:#bbf,stroke:#333
    style C fill:#bbf,stroke:#333

The Two Core Operations

Because of this LSB responsibility rule, navigating the tree is incredibly simple.

1. Query: Finding the Prefix Sum (Moving Down)

To find the sum from index 1 to index $i$, we start at $i$, add tree[i] to our total, and then subtract the LSB to jump to the next responsible index. We repeat until we hit 0.

Interactive Example: query(7)

Start at 7. Add tree[7].
  ↓ (7 - LSB(1) = 6)
Jump to 6. Add tree[6].
  ↓ (6 - LSB(2) = 4)
Jump to 4. Add tree[4].
  ↓ (4 - LSB(4) = 0)
Hit 0. Done!

Total Sum = tree[7] + tree[6] + tree[4]

2. Update: Point Update (Moving Up)

When an element at index $i$ changes, we start at $i$, update tree[i], and then add the LSB to jump to the parent index.

Interactive Example: update(5, delta)

Start at 5. Update tree[5].
  ↓ (5 + LSB(1) = 6)
Jump to 6. Update tree[6].
  ↓ (6 + LSB(2) = 8)
Jump to 8. Update tree[8].
  ↓ (8 + LSB(8) = 16)
Jump to 16. (Out of bounds, stop!)

How does it answer Range Sums?

If BIT only computes prefix sums, how can it answer range sums? By subtracting two prefixes!

Range Sum(l, r) = Prefix(r) - Prefix(l - 1)

The Implementation (Python)

Here is the clean, production-ready Fenwick Tree implementation in Python.

⚠️ Crucial Rule: Fenwick Trees are 1-indexed. If your problem uses a 0-indexed array, you must offset your indices by 1. If you try to use index 0, LSB(0) = 0, and your while loops will infinite loop!

class FenwickTree:
    def __init__(self, size):
        self.n = size
        self.bit = [0] * (size + 1)

    def _lsb(self, i):
        return i & -i

    # Add 'delta' to the element at index 'i' (1-indexed)
    def update(self, i, delta):
        while i <= self.n:
            self.bit[i] += delta
            i += self._lsb(i) # Move UP the tree

    # Get the sum of elements from index 1 to 'i' (1-indexed)
    def query(self, i):
        total = 0
        while i > 0:
            total += self.bit[i]
            i -= self._lsb(i) # Move DOWN the tree
        return total

    # Get sum from index 'left' to 'right' (1-indexed, inclusive)
    def range_sum(self, left, right):
        return self.query(right) - self.query(left - 1)

The $O(N)$ Build Method

If an interviewer asks, "Can we build this faster than $O(N \log N)$?", impress them with the linear time build. You populate the array directly, then push the values up to the parents.

def build_linear(self, arr):
    n = len(arr)
    self.bit = [0] + arr[:] # 1-indexed copy
    for i in range(1, n + 1):
        parent = i + (i & -i)
        if parent <= n:
            self.bit[parent] += self.bit[i]

Complexity Analysis

Fenwick Tree vs. Segment Tree

In interviews, you might wonder when to use a Fenwick Tree over a Segment Tree. Both solve the same fundamental problem, but with different tradeoffs.

The Golden Rule: If the operation is invertible (e.g., Sum: Range(i, j) = Prefix(j) - Prefix(i-1)), use a Fenwick Tree. If the operation is non-invertible (e.g., Min, Max: you cannot find the min of a range just by knowing the prefix mins), you must use a Segment Tree.

🧠 How to Remember It (Cheat Sheet)

Think of it this way: * Query climbs toward the root by subtracting the LSB (i -= i & -i). * Update climbs toward larger responsibility ranges by adding the LSB (i += i & -i). * Prefix sum → direct query * Range sum → subtract two prefixes (query(r) - query(l-1)) * Indexing → Always 1-indexed

Real Interview Questions & Practice Problems

Frequently Asked Questions (FAQ)

Why is Fenwick Tree 1-indexed? Because the bitwise operation x & -x isolates the lowest set bit. For x = 0, 0 & 0 = 0. If we used 0-indexing, our while i > 0 loops would terminate instantly, and our while i <= n update loops would infinite loop.

Is Fenwick Tree faster than Segment Tree? Yes, in practice. While both are $O(\log N)$, BIT has a much smaller constant factor, uses less memory, and performs simple array iterations rather than recursive tree traversals.

Can Fenwick Tree store minimum/maximum? No, not easily. Subtraction doesn't work for minimums (e.g., min(1..5) - min(1..3) does not give you min(4..5)). For Range Minimum Queries (RMQ), use a Segment Tree.

Can Fenwick Tree perform range updates? Yes! By using two BITs, you can perform Range Updates and Point Queries, or even Range Updates and Range Queries. This is an advanced topic often asked in hard LeetCode problems.

Conclusion

If your problem requires frequent point updates and prefix or range sum queries, a Fenwick Tree is usually the simplest and fastest solution. It offers the same $O(\log N)$ query and update complexity as a Segment Tree for sum operations while using less memory and requiring far less code.