Fenwick Tree: Binary Indexed Tree for Range Sums Explained with Examples

The Fenwick Tree, also called the Binary Indexed Tree (BIT), is a powerful data structure used for efficiently performing prefix sum (cumulative frequency) queries and updates on an array. Unlike a naive prefix sum array which requires O(n) time to update, a Fenwick Tree enhances performance by reducing the update and query operations to O(log n).

This makes it indispensable in competitive programming, range query problems, and applications like inversion counting, frequency tables, and prefix calculations.

Table of Contents

Why Fenwick Tree Instead of Simple Prefix Sums?

A simple prefix sum array can answer sum queries in O(1), but requires O(n) time for updates.
A Fenwick Tree answers queries in O(log n) and updates also in O(log n).
This balance makes it ideal where you have many updates and queries mixed together.

How Does the Fenwick Tree Work?

A Fenwick Tree cleverly uses the binary representation of indices to reduce the number of elements considered when storing or retrieving prefix sums.

Key idea: For index i, the Fenwick Tree array BIT stores the sum of elements from i - (i & -i) + 1 to i, where (i & -i) gives the last set bit of i.

Construction of Fenwick Tree

We start with an initial array and build BIT by updating values iteratively.

Example

Consider array: [3, 2, -1, 6, 5, 4, -3, 3]

Initial Array (arr):
Index:  1   2   3   4   5   6   7   8
Value:  3   2  -1   6   5   4  -3   3

Fenwick Tree (BIT) representation:
Index:  1   2   3   4   5   6   7   8
Value:  3   5  -1  10   5   9  -3  19

Operations in Fenwick Tree

1. Update Operation

To update index i with a new value difference delta, you repeatedly add delta to BIT[i] and move to i + (i & -i).


def update(bit, n, idx, delta):
    while idx <= n:
        bit[idx] += delta
        idx += idx & -idx

2. Prefix Sum Query

To compute prefix sum till index i, you accumulate contributions from BIT until i becomes 0.


def prefix_sum(bit, idx):
    result = 0
    while idx > 0:
        result += bit[idx]
        idx -= idx & -idx
    return result

3. Range Sum Query

Using prefix sums, a range sum query becomes:


def range_sum(bit, left, right):
    return prefix_sum(bit, right) - prefix_sum(bit, left-1)

Visual Demonstration

Suppose we want to find sum from index 2 to 5 in the array.

Interactive Example

Here is a small Python demonstration showing updates and queries in action:


arr = [0, 3, 2, -1, 6, 5, 4, -3, 3]  # 1-indexed
n = len(arr) - 1 
bit = [0]*(n+1)

# Build BIT
for i in range(1, n+1):
    update(bit, n, i, arr[i])

print("Prefix sum till index 5:", prefix_sum(bit, 5))   # Output: 15
print("Range sum (2 to 5):", range_sum(bit, 2, 5))      # Output: 12

# Update operation (add 2 at index 3)
update(bit, n, 3, 2)
print("Range sum (2 to 5) after update:", range_sum(bit, 2, 5))  # Output changes

Complexity Analysis

Construction: O(n log n) (or O(n) with optimized build)
Update: O(log n)
Prefix Sum: O(log n)
Range Sum: O(log n)
Space: O(n)

Applications of Fenwick Tree

Efficient range sum and frequency queries.
Inversion count in an array (used in sorting problems).
Finding order statistics with frequency arrays.
2D Fenwick Tree used in computational geometry.
Practical in coding competitions where frequent updates and queries are required.

Conclusion

The Fenwick Tree is one of the most elegant data structures that balances speed and space efficiency. It is a must-have tool in every programmer’s arsenal for handling range sum queries and dynamic cumulative frequencies. Understanding its binary representation trick provides deeper insight into efficient algorithm design.