Interview Guide: Fenwick Trees Problems and Solutions

What is a Fenwick Tree?

A Fenwick Tree, also known as a Binary Indexed Tree (BIT), is a data structure that efficiently handles prefix sum queries and point updates on an array of numbers. It was first described by Peter M. Fenwick in 1994. Unlike a Segment Tree, which uses a full binary tree and requires more memory, a Fenwick Tree uses a flat array of the same size as the original data and performs operations in O(log n) time with very low constant overhead.

At its core, the Fenwick Tree stores cumulative sums for specific ranges of indices. By exploiting the binary representation of an index, it can quickly jump to the correct nodes to sum a prefix or propagate an update. It supports two main operations:

• Point Update: add a value to an element at position i.
• Prefix Query: retrieve the sum of elements from index 1 to i (in 1-based indexing).

With prefix queries, you can easily compute a range sum between indices l and r as query(r) - query(l-1).

Why It Matters for Interviews

Fenwick Trees appear regularly in coding interviews, especially at large tech companies like Google, Meta, and Amazon. The structure is a go-to tool whenever the problem statement includes:

• Frequent updates to array elements (e.g., dynamic array modification).
• Frequent range sum queries that must be answered fast.
• Counting elements with relative order (inversions, smaller elements after self).
• Problems requiring a dynamic cumulative frequency table.

Compared to a simple array, where updates are O(1) but range sum queries are O(n), and a prefix sum array that gives O(1) queries but O(n) updates, the Fenwick Tree achieves O(log n) for both. This balance makes it ideal for problems with mixed workloads. Interviewers love it because it tests a candidate’s understanding of bit manipulation, tree flattening, and algorithmic optimization.

Core Concepts: How It Works

The Fenwick Tree uses a clever indexing scheme based on the least significant bit (LSB). For an index i (1-based), the node at tree[i] is responsible for the sum of a range of elements ending at i and whose length is exactly the value of the lowest set bit in i.

For example:

• i = 4 (binary 100, LSB = 4) → tree[4] covers indices 1..4.
• i = 5 (binary 101, LSB = 1) → tree[5] covers only index 5.
• i = 6 (binary 110, LSB = 2) → tree[6] covers indices 5..6.

Prefix sum query works by repeatedly adding tree[i] and then removing the LSB from i (i.e., moving to a parent that covers the remaining part). This is achieved by i -= i & -i. Point update works by adding the delta to tree[i] and then propagating the change to all nodes that cover ranges containing i, by moving to the next node using i += i & -i.

Visualizing the tree for n = 8

Index:    1   2   3   4   5   6   7   8
Binary: 001 010 011 100 101 110 111 1000
Cover:  1   1-2 3   1-4 5   5-6 7   1-8

Notice how tree[8] stores the total sum of indices 1 to 8. tree[2] stores sum of indices 1-2, tree[4] stores sum of 1-4. The structure is a forest of trees, each representing a different coverage scope.

Implementation in Code

Below is a complete Python implementation of a Fenwick Tree class with methods for point update and prefix/range sum queries. The implementation uses 1-based indexing internally for clarity and simplicity.

class FenwickTree:
    def __init__(self, n: int):
        # Store tree as 1-indexed array of size n+1
        self.n = n
        self.tree = [0] * (n + 1)

    def update(self, i: int, delta: int) -> None:
        """Add delta to original array at index i (1-based)."""
        while i <= self.n:
            self.tree[i] += delta
            i += i & -i   # move to next node that covers i

    def query(self, i: int) -> int:
        """Return prefix sum from 1 to i (inclusive)."""
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i   # move to parent node
        return s

    def range_sum(self, l: int, r: int) -> int:
        """Return sum of elements from l to r (1-based)."""
        return self.query(r) - self.query(l - 1)

Usage example:

# Original array: [3, 2, -1, 6, 5, 4]
arr = [3, 2, -1, 6, 5, 4]
bit = FenwickTree(len(arr))

# Build tree by updating each position with initial value
for i, val in enumerate(arr, start=1):
    bit.update(i, val)

# Prefix sum up to index 4: 3+2-1+6 = 10
print(bit.query(4))  # Output: 10

# Range sum from index 2 to 5: 2+(-1)+6+5 = 12
print(bit.range_sum(2, 5))  # Output: 12

# Update: add 3 to element at index 3 (was -1, becomes 2)
bit.update(3, 3)
print(bit.range_sum(2, 5))  # Now: 2+2+6+5 = 15

Common Interview Problems and Solutions

1. Range Sum Query - Mutable (LeetCode 307)

Problem: Given an integer array, handle multiple updates to elements and queries that ask for the sum of elements between indices left and right.

Solution: Direct application of the Fenwick Tree class shown above. Build the tree in O(n log n) by calling update for each initial element, or optimize to O(n) by using a linear construction technique. For each query, call range_sum(left, right).

class NumArray:
    def __init__(self, nums: List[int]):
        self.nums = nums
        self.n = len(nums)
        self.bit = FenwickTree(self.n)
        for i, val in enumerate(nums, 1):
            self.bit.update(i, val)

    def update(self, index: int, val: int) -> None:
        delta = val - self.nums[index]
        self.nums[index] = val
        self.bit.update(index + 1, delta)  # +1 for 1-based BIT

    def sumRange(self, left: int, right: int) -> int:
        return self.bit.range_sum(left + 1, right + 1)

2. Count of Smaller Numbers After Self (LeetCode 315)

Problem: For each element in an array, count how many elements to its right are strictly smaller than it.

Solution: Use coordinate compression (map values to ranks 1..N) and a Fenwick Tree to keep frequency counts. Process the array from right to left. For each element, query the BIT for the count of numbers smaller than its rank (i.e., prefix sum up to rank-1), then update the BIT by adding 1 at its rank.

def countSmaller(nums):
    # Coordinate compression: sorted unique values -> ranks 1..m
    sorted_unique = sorted(set(nums))
    rank_map = {v: i+1 for i, v in enumerate(sorted_unique)}  # 1-based
    m = len(sorted_unique)
    bit = FenwickTree(m)
    result = []
    # Traverse from right to left
    for num in reversed(nums):
        rank = rank_map[num]
        # Count numbers smaller than current (ranks 1 to rank-1)
        smaller = bit.query(rank - 1)
        result.append(smaller)
        # Insert current number
        bit.update(rank, 1)
    return result[::-1]  # reverse to match original order

3. Range Sum Query 2D - Mutable

Problem: Support point updates and submatrix sum queries in a 2D grid.

Solution: Use a Fenwick Tree of Fenwick Trees (2D BIT). Each row’s BIT is updated via a nested BIT. Alternatively, maintain a 2D array of size (rows+1) x (cols+1) where tree[x][y] stores cumulative sums for rectangles. Update and query loops use the same i += i & -i pattern on both dimensions.

class Fenwick2D:
    def __init__(self, rows, cols):
        self.rows = rows
        self.cols = cols
        self.tree = [[0]*(cols+1) for _ in range(rows+1)]

    def update(self, x, y, delta):
        i = x
        while i <= self.rows:
            j = y
            while j <= self.cols:
                self.tree[i][j] += delta
                j += j & -j
            i += i & -i

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

    def range_sum(self, r1, c1, r2, c2):
        # Standard 2D prefix sum inclusion-exclusion
        return (self.query(r2, c2) 
                - self.query(r1-1, c2) 
                - self.query(r2, c1-1) 
                + self.query(r1-1, c1-1))

4. Reverse Pairs (LeetCode 493)

Problem: Count pairs (i, j) where i < j and nums[i] > 2 * nums[j].

Solution: Similar to count of smaller numbers, compress both original values and doubled values, then use a BIT to track frequencies while iterating from left to right (or right to left). The BIT helps query how many previously seen elements are strictly greater than 2 * current.

5. Dynamic Cumulative Frequency Tables

Many problems involving dynamic order statistics, like finding the k-th smallest element in a stream with deletions, can be tackled with a Fenwick Tree over a frequency array combined with binary search on the prefix sums (using binary lifting on the BIT itself for O(log n) find).

Best Practices and Tips

• 1-based indexing is mandatory. The core bit operations rely on the lowest set bit. If your problem uses 0-based indices, add 1 when calling update/query, and subtract 1 when converting results.
• Coordinate compression: When the values are not small contiguous integers, map them to ranks. This is essential for frequency-based BITs in problems like counting inversions.
• Linear construction: You can build a BIT in O(n) by first accumulating prefix sums into a temporary array and then assigning tree[i] as the sum of the appropriate range. This avoids n log n initialization overhead when n is large.
• Use meaningful variable names: i += i & -i (next node) and i -= i & -i (parent node) are idiomatic, but comment them for clarity.
• Range updates and point queries: A Fenwick tree can also support adding a value to all elements in a range and querying a single point. This requires a different BIT configuration (difference array technique) but still O(log n). Know this variant.
• Non-numeric operations: The Fenwick tree is not limited to sums. It works with any invertible associative operation (e.g., XOR, multiplication modulo something), provided the operation has an inverse. For non-invertible operations (like max), segment trees are required.
• 2D BITs: Be careful with memory – a 2D BIT is O(n*m). If constraints are high, consider alternative approaches like coordinate compression on both axes or using a segment tree.
• Binary lifting for order statistics: Instead of binary searching the prefix sum, you can use the BIT’s tree structure to walk from the most significant bit downward to find the smallest index with a given cumulative frequency, achieving O(log n) without external search.

Conclusion

The Fenwick Tree is a lightweight yet powerful data structure that belongs in every serious developer’s interview toolkit. It offers logarithmic time complexity for prefix sums and point updates using a minimal memory footprint. Mastering its implementation—especially the bit manipulation traversal—signals strong algorithmic maturity. Practice the classic problems like range sum mutable, count of smaller numbers, and 2D range queries to build muscle memory. Remember to handle indexing carefully, compress values when needed, and explore variants like range updates. With these skills, you’ll confidently tackle any interview question where dynamic cumulative information is key.