Fenwick Tree (Binary Indexed Tree)

Generated on 2025-07-10 02:05:14 Algorithm Cheatsheet for Technical Interviews

---

Fenwick Tree (Binary Indexed Tree) Cheat Sheet

1. Quick Overview

A Fenwick Tree (also known as a Binary Indexed Tree or BIT) is a data structure that efficiently calculates prefix sums and supports updates on an array. It’s particularly useful when you need to perform both of these operations frequently.

When to use it:

• When you need both prefix sum calculations and array updates.
• When space efficiency is a concern (compared to segment trees).
• When the problem involves cumulative frequency calculations.

2. Time & Space Complexity

Operation	Time Complexity
Update	O(log n)
Prefix Sum Query	O(log n)
Space Complexity	O(n)

n is the size of the input array.

3. Implementation

Here’s the implementation in Python, Java, and C++ with detailed comments:

Python:

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

    def update(self, i, delta):
        """
        Updates the value at index i by adding delta to it.
        Time Complexity: O(log n)
        """
        i += 1 # Convert to 1-based indexing
        while i <= self.n:
            self.tree[i] += delta
            i += i & -i  # Move to the next node responsible for the index

    def prefix_sum(self, i):
        """
        Calculates the prefix sum from index 0 to i (inclusive).
        Time Complexity: O(log n)
        """
        i += 1 # Convert to 1-based indexing
        sum_val = 0
        while i > 0:
            sum_val += self.tree[i]
            i -= i & -i  # Move to the parent node
        return sum_val

    def range_sum(self, i, j):
        """
        Calculates the sum in the range [i, j] (inclusive).
        Time Complexity: O(log n)
        """
        return self.prefix_sum(j) - self.prefix_sum(i - 1) if i > 0 else self.prefix_sum(j)

# Example Usage
if __name__ == "__main__":
    arr = [1, 7, 3, 0, 5, 8, 3, 2, 6, 2, 1, 1, 4, 5]
    n = len(arr)
    ft = FenwickTree(n)

    # Initialize the Fenwick Tree with the array values
    for i in range(n):
        ft.update(i, arr[i])

    print("Prefix sum up to index 5:", ft.prefix_sum(5))  # Output: 24 (1+7+3+0+5+8)
    print("Range sum from index 2 to 7:", ft.range_sum(2, 7)) # Output: 19 (3+0+5+8+3+2)
    ft.update(3, 5)  # Update element at index 3 by adding 5
    print("Prefix sum up to index 5 after update:", ft.prefix_sum(5)) # Output: 29 (1+7+3+5+5+8)

Java:

class FenwickTree {
    private int[] tree;
    private int n;

    public FenwickTree(int n) {
        this.n = n;
        this.tree = new int[n + 1]; // 1-indexed array
    }

    public void update(int i, int delta) {
        // Time Complexity: O(log n)
        i++; // Convert to 1-based indexing
        while (i <= n) {
            tree[i] += delta;
            i += i & -i; // Move to the next node responsible for the index
        }
    }

    public int prefixSum(int i) {
        // Time Complexity: O(log n)
        i++; // Convert to 1-based indexing
        int sum = 0;
        while (i > 0) {
            sum += tree[i];
            i -= i & -i; // Move to the parent node
        }
        return sum;
    }

    public int rangeSum(int i, int j) {
        // Time Complexity: O(log n)
        return (i > 0) ? prefixSum(j) - prefixSum(i - 1) : prefixSum(j);
    }

    public static void main(String[] args) {
        int[] arr = {1, 7, 3, 0, 5, 8, 3, 2, 6, 2, 1, 1, 4, 5};
        int n = arr.length;
        FenwickTree ft = new FenwickTree(n);

        // Initialize the Fenwick Tree with the array values
        for (int i = 0; i < n; i++) {
            ft.update(i, arr[i]);
        }

        System.out.println("Prefix sum up to index 5: " + ft.prefixSum(5)); // Output: 24 (1+7+3+0+5+8)
        System.out.println("Range sum from index 2 to 7: " + ft.rangeSum(2, 7)); // Output: 19 (3+0+5+8+3+2)
        ft.update(3, 5); // Update element at index 3 by adding 5
        System.out.println("Prefix sum up to index 5 after update: " + ft.prefixSum(5)); // Output: 29 (1+7+3+5+5+8)
    }
}

C++:

#include <iostream>
#include <vector>

class FenwickTree {
private:
    std::vector<int> tree;
    int n;

public:
    FenwickTree(int n) : n(n), tree(n + 1, 0) {}  // 1-indexed array

    void update(int i, int delta) {
        // Time Complexity: O(log n)
        i++; // Convert to 1-based indexing
        while (i <= n) {
            tree[i] += delta;
            i += i & -i;  // Move to the next node responsible for the index
        }
    }

    int prefixSum(int i) {
        // Time Complexity: O(log n)
        i++; // Convert to 1-based indexing
        int sum = 0;
        while (i > 0) {
            sum += tree[i];
            i -= i & -i;  // Move to the parent node
        }
        return sum;
    }

    int rangeSum(int i, int j) {
        // Time Complexity: O(log n)
        return (i > 0) ? prefixSum(j) - prefixSum(i - 1) : prefixSum(j);
    }
};

int main() {
    std::vector<int> arr = {1, 7, 3, 0, 5, 8, 3, 2, 6, 2, 1, 1, 4, 5};
    int n = arr.size();
    FenwickTree ft(n);

    // Initialize the Fenwick Tree with the array values
    for (int i = 0; i < n; i++) {
        ft.update(i, arr[i]);
    }

    std::cout << "Prefix sum up to index 5: " << ft.prefixSum(5) << std::endl; // Output: 24 (1+7+3+0+5+8)
    std::cout << "Range sum from index 2 to 7: " << ft.rangeSum(2, 7) << std::endl; // Output: 19 (3+0+5+8+3+2)
    ft.update(3, 5); // Update element at index 3 by adding 5
    std::cout << "Prefix sum up to index 5 after update: " << ft.prefixSum(5) << std::endl; // Output: 29 (1+7+3+5+5+8)

    return 0;
}

4. Common Patterns

• Range Sum Queries: The most common use case.
• Point Updates: Updating a single element in the array.
• Frequency Counting: Calculating cumulative frequencies efficiently.
• 2D Fenwick Tree: Extend the concept to 2D arrays for range sum queries and point updates in a matrix.
• Inversion Counting: Counting the number of inversions in an array (pairs of elements where arr[i] > arr[j] and i < j).
• Range Updates (Difference Array): Achieve range updates in O(log n) by using a Fenwick Tree on the difference array. This allows adding a value to a range of elements.

5. Pro Tips

• 1-Based Indexing: Fenwick Trees are typically implemented using 1-based indexing for easier calculations using bit manipulation.
• Bit Manipulation: i & -i is the key operation. It extracts the least significant bit of i (the rightmost set bit). This is used to navigate the tree structure.
• Initialization: To initialize a Fenwick Tree from an existing array, you can either iterate and update(i, arr[i]) for each element, or you can build it directly using the properties of the tree (more efficient for large arrays).
• Difference Array for Range Updates: If you need to perform range updates frequently, use a difference array. Let diff[i] = arr[i] - arr[i-1]. Update diff using Fenwick Tree. Then, arr[i] can be found as the prefix sum of diff up to i.
• Avoid Overflows: Be mindful of potential integer overflows when dealing with large sums. Use long or long long where necessary.

6. Practice Problems

Here are some LeetCode-style problems that can be solved using Fenwick Trees:

1. LeetCode 307. Range Sum Query - Mutable: Implement sumRange and update operations. (Classic Fenwick Tree application).
2. LeetCode 315. Count of Smaller Numbers After Self: Use Fenwick tree to count smaller elements on the right of each element.
3. LeetCode 493. Reverse Pairs: Using Fenwick Tree to count reverse pairs.

7. Templates

Here are reusable code snippets for Fenwick Tree operations in Python, Java, and C++

Python:

class FenwickTreeTemplate:
    def __init__(self, size):
        self.size = size
        self.tree = [0] * (size + 1)

    def update(self, index, value):
        index += 1
        while index <= self.size:
            self.tree[index] += value
            index += index & -index

    def query(self, index):
        index += 1
        result = 0
        while index > 0:
            result += self.tree[index]
            index -= index & -index
        return result

Java:

class FenwickTreeTemplate {
    private int[] tree;
    private int size;

    public FenwickTreeTemplate(int size) {
        this.size = size;
        this.tree = new int[size + 1];
    }

    public void update(int index, int value) {
        index++;
        while (index <= size) {
            tree[index] += value;
            index += index & -index;
        }
    }

    public int query(int index) {
        index++;
        int result = 0;
        while (index > 0) {
            result += tree[index];
            index -= index & -index;
        }
        return result;
    }
}

C++:

#include <vector>

class FenwickTreeTemplate {
private:
    std::vector<int> tree;
    int size;

public:
    FenwickTreeTemplate(int size) : size(size), tree(size + 1, 0) {}

    void update(int index, int value) {
        index++;
        while (index <= size) {
            tree[index] += value;
            index += index & -index;
        }
    }

    int query(int index) {
        index++;
        int result = 0;
        while (index > 0) {
            result += tree[index];
            index -= index & -index;
        }
        return result;
    }
};

This cheat sheet provides a comprehensive overview of Fenwick Trees, making it a valuable resource for developers. Remember to adapt the code and concepts to your specific problem requirements. Good luck!