Fenwick Tree (Binary Indexed Tree)

Definition

A Fenwick Tree is a clever data structure that does exactly what a Segment Tree does (Prefix Sums and Updates) but uses less memory and is easier to code. It relies heavily on binary bit manipulation.

How it Works

Unlike a standard array where index i holds value i, in a Fenwick Tree, index i holds the sum of a specific range determined by the Least Significant Bit (LSB) of i. It allows you to jump through the array in powers of 2 to calculate sums.

Real-World Analogy:

Imagine a Bucket System for collecting coins.

• Bucket 1 holds coins from day 1.
• Bucket 2 holds coins from day 1-2.
• Bucket 4 holds coins from day 1-4.
  To find the total for 13 days, you don’t add 13 buckets. You grab the “Day 1-8” bucket, the “Day 9-12” bucket, and the “Day 13” bucket. Just 3 steps!

Code Example (Python)

Python

def update(BIT, n, i, val):
    i += 1  # 1-based indexing
    while i <= n:
        BIT[i] += val
        i += i & (-i) # Add LSB to move to next node

def query(BIT, i):
    i += 1  # 1-based indexing
    s = 0
    while i > 0:
        s += BIT[i]
        i -= i & (-i) # Subtract LSB to move to parent
    return s

arr = [1, 2, 3, 4, 5]
n = len(arr)
BIT = [0] * (n + 1)

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

print(“Sum of first 3 elements:”, query(BIT, 2))

# Output: 6 (1+2+3)

Complexity Analysis

• Time Complexity:

• Update: O(log n)
• Query: O(log n)

• Space Complexity: O(n) (Uses same space as the input array, unlike Segment Tree).

Use Cases

• Cumulative Frequencies: Often used in data compression algorithms.
• Counting Inversions: Used to measure how “unsorted” an array is.
• Gaming Leaderboards: Calculating ranks dynamically.