Fenwick Tree (Binary Indexed Tree)

Fenwick Tree, also known as the Binary Indexed Tree (BIT) is a data structure used for efficiently solving problems involving prefix sums and range queries. In this post, we’ll understand what a Fenwick Tree is, how does it work, its applications, and how to implement it in C++ for sum queries.

Prerequisite: Understanding RMQ (Range Minimum Query)

What is a Fenwick Tree?

A Fenwick Tree, or Binary Indexed Tree, is a data structure that allows efficient computation of prefix sums and range sum queries in logarithmic time. It is particularly useful when the array you’re working with changes dynamically and requires frequent updates.

Key Characteristics

• Requires only O(n) space to store an array of size n.
• Supports both updates and prefix sum queries in O(logn) time.

Basic Operations

• Prefix Sum Query: Computing the sum of elements from the start of the array to a given index.
• Update: Modifying the value of an element in the array and propagating this change to relevant nodes in the Fenwick tree.

Applications and Use-Cases

Fenwick Tree is used in various scenarios where efficient sum queries and updates are needed. While its most common use is for range sum queries, it can be adapted to support other types of range queries as well, with some modifications to the structure and update rules.

General Rule
Fenwick Trees excel at handling operations that are:

• Associative: The operation can be combined in a cumulative way (like sum, multiplication, XOR, GCD).
• Cumulative: The operation can be broken down into smaller parts, such as querying prefixes and then combining them to get the desired range result.

Applications of Fenwick Tree

1. Prefix Sum Queries: Calculating the sum of elements from the start of the array to any given index in O(logn).
2. Range Queries: With some modifications, it can handle range queries such as range product, minimum, or maximum etc.
3. Inversion Counting: In competitive programming, the Fenwick Tree is often used to solve problems like counting the number of inversions in an array in O(nlog⁡n) etc.
4. Dynamic Cumulative Frequency Tables: Maintaining cumulative frequency tables where updates and queries are frequent.

Intuition Behind the Fenwick Tree

A Fenwick Tree is conceptually an array that uses the binary representation of indices to store and update sums of subarrays. The main idea behind the Fenwick Tree is to represent the array in such a way that every node in the tree stores information about a range of elements in the original array. The key is to divide the array into groups or subarrays based on the binary representation of indices, which allows us to efficiently combine the results of smaller subranges to answer range sum queries.

– Each node BIT[i] in the Fenwick Tree stores the sum of a specific range/subarray of elements in the original array.
– The size of the subarray (arr[starti] + .. + arr[endi]) associated with each index i of Fenwick Tree is determined by the lowest set bit in the binary representation of the number i.

(each tree node will store the sum of consecutive array elements ie. subarrays are contiguous)

Binary Representation and Subarrays

The Fenwick Tree exploits the binary representation of indices to determine which range of elements should be summed and stored at each node index. The node at position i in the Fenwick Tree represents the sum of the last 2r elements ending at index i in the original array, where r is the position of the rightmost set bit of i in its binary representation.

Note: For simplicity and consistency with the Fenwick Tree structure (which uses 1-based indexing), I'll use 1-based indexing for the input array throughout this explanation.

Pseudocode

Let’s consider a Fenwick Tree (BIT[]) that handles sum queries. The tree will support two main operations:

1. Update: Update an element in the array.
2. Sum Query: Calculate the sum of elements from index 1 to some index i.

Update

update(BIT[], idx, val, n)
    while idx <= n do
        BIT[idx] = BIT[idx] + val
        idx = idx + (idx & -idx)

Query

query(BIT[], idx)
    sum = 0
    while idx > 0 do
        sum = sum + BIT[idx]
        idx = idx - (idx & -idx)
    return sum

Range Sum

range_sum(BIT[], L, R)
    return query(BIT, R) - query(BIT, L-1)

Explanation

• idx & -idx extracts the rightmost ‘set bit’ (bit having value 1) of idx.
• The update() procedure adds val to the element at index idx and updates all related nodes that are affected by this change. (this same method is used for creating Fenwick Tree BIT[] for the input array arr[], which we’ll discuss later)
• Adding idx & -idx to idx moves index idx to the next node (containing a larger range of values) in BIT[] which contains arr[idx].
• The query() procedure calculates the prefix sum from the start of the input array to index idx.
• Subtracting idx & -idx from idx clears the rightmost set bit of idx, leaving all the bits before it unchanged, essentially moving to the parent node and summing up the remaining values along the way.
• The range_sum() procedure computes the sum of elements between two indices L and R (both inclusive) using query().

It is important to note that -idx in (idx & -idx) represents the two's complement of the number idx. 

Here's how it works:

For example, consider idx = 5 in binary:

idx   = 0101
~idx  = 1010  // Bitwise NOT of idx
-idx  = 1011  // Add 1 to the result (~idx + 1)

idx & -idx gives:
0101 & 1011 = 0001, which is the the rightmost set bit of idx (in this case, 5).

Example

For simplicity, consider this array: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]. This array has 15 elements (ignore arr[0]). Let’s look at the subarrays stored at each node in a Fenwick Tree for this input array,

We will use 1-based indexing for Fenwick Tree also (as is typical with Fenwick Trees).

Here are some things that can be observed from the above Fenwick Tree:

• For each index (idx), the subarray it covers is based on the rightmost set bit of idx.

• The cumulative sum stored at BIT[idx] includes elements from index idx – (idx & – idx) + 1 to idx .

We know that, 
2r = idx & -idx, where r is the rightmost set bit (0-based) of idx

Let's consider the index 12 (1100), we have r = 2
the subarray sum stored at BIT[12] corresponds to the range: idx − (idx & −idx) + 1 to idx

Substituting the values, we get:
range start = idx − (idx & −idx) + 1 = 12 - 4 + 1 = 9
range end = idx = 12

hence, the subarray sum stored at BIT[12] is:
9 + 10 + 11 + 12 (arr[9]..arr[12])

• Each odd node (like index 1, 3, 5, etc.) contains only one element.
• That odd node element is then added to the immediate next even node (like index 2, 4, 6, etc).
• If node index is a power of 2, it’ll contain all elements starting from 1 up to that node index.

Understanding the Working of Fenwick Tree

The Fenwick Tree stores partial sums for subarrays based on the binary representation of indices. It combines the power of binary operations and cumulative sums to perform update and query operations in O(logn) time. The ability to jump from node to node by clearing or setting the lowest set bit means that both the query and update operations are logarithmic.

Let’s say we want to query the sum from index 1 to 5. The Fenwick Tree would efficiently compute the sum by combining precomputed results from different parts of the array.

The prefix sum up to an index idx can be broken down into several smaller subarrays, such that size of each, corresponds to a power of 2. The Fenwick Tree stores the cumulative sum of these subarrays in such a way that a query can retrieve the complete prefix sum by combining a few precomputed sums.

Query Operation (Prefix Sum Query)

The process of querying the prefix sum from index 1 to idx involves combining the partial sums stored in the nodes of the Fenwick Tree. The key idea is to decompose the range [1, idx] into disjoint subranges, each of which corresponds to a value stored in BIT[].

To compute the prefix sum up to index idx, we combine the sums stored at several positions in the Fenwick Tree. The logic:

1. Start at index idx
2. Add the value at BIT[idx] to the cumulative sum.
3. Move to the parent node using idx = idx - (idx & -idx)

Continue this process, until idx becomes 0

Consider this array,

arr[] = {a1, a2, a3, a4, a5, a6, a7, a8}

We want to compute the prefix sum S7 from a1 to a7

Starting at a7 ie. index idx = 7 (01112): 
sum = 0

BIT[7] = a7
sum = sum + BIT[7] = a7
idx = 7 - 1 = 6

BIT[6] = a5 + a6
sum = sum + BIT[6] = a5 + a6 + a7
idx = 6 - 2 = 4

BIT[4] = a1 + a2 + a3 + a4
sum = sum + BIT[4] = a1 + a2 + a3 + a4 + a5 + a6 + a7
idx = 4 - 4 = 0

Note: Computing the cumulative sum S in a Fenwick Tree seems similar to computing the decimal value of a binary number. This stems from the decomposition of the range [1, idx] into disjoint subranges, mirroring the structure of binary representation.

Update Operation

void update(int idx, int delta) {
    while (idx <= n) {
        BIT[idx] += delta;  // Update BIT at idx by adding delta
        idx += idx & -idx;  // Move to the next index that needs updating
    }
}

• idx: the index of the element that we are updating
• delta: the amount to be added to the value at index idx (can be negative)

The update operation ensures that the delta is added to all relevant nodes in the Fenwick Tree that include arr[idx]. This is because of the way we create the Fenwick Tree and the structure of the tree, where each node represents a sum over specific ranges.

Fenwick Tree Construction (Binary Decomposition)

The central idea behind the Fenwick Tree is to decompose the prefix sums of an array into disjoint subranges. This allows us to compute a range sum by combining these smaller precomputed sums, ensuring that any prefix sum can be queried in logarithmic time.

To understand this remember that in a Fenwick Tree each node (or index) represents a cumulative sum over a range that corresponds to the powers of two.

    void update(int idx, int delta) {
        while (idx <= n) {
            BIT[idx] += delta;  // Update the node
            idx += idx & -idx;  // Move to the next index
        }
    }

    // Build the Fenwick Tree with initial values
    for (int i = 1; i <= n; i++) {
        fenwickTree.update(i, arr[i-1]);
    }

Explanation

For each index i, we call the update() method, where the value arr[i-1] (in practice, we use arr[i-1] and not arr[i]) is added to the node i in the Fenwick Tree. After updating the node, the change is propagated through the tree, ensuring all nodes that include arr[i-1] in their cumulative sum are updated.

We construct the Fenwick Tree using the update() method, where each node is iteratively updated with its corresponding value from the input array. Consequently, when a node is updated via the update() method, the change is propagated to all nodes that include arr[i-1].

Code Implementation

//
//  main.cpp
//  Fenwick Tree
//
//  Created by Himanshu on 03/10/24.
//

#include <iostream>
#include <vector>
using namespace std;

class FenwickTree {
    vector<int> BIT;  // Binary Indexed Tree
    int n;

public:
    // Constructor to initialize Fenwick Tree of size n
    FenwickTree(int size) {
        n = size;
        BIT.assign(n+1, 0);  // Initialize tree with 0 values
    }

    // Update the value at index idx by delta
    void update(int idx, int delta) {
        while (idx <= n) {
            BIT[idx] += delta;
            idx += idx & -idx;  // Move to the next index
        }
    }

    // Query the prefix sum from index 1 to idx
    int query(int idx) {
        int sum = 0;

        while (idx > 0) {
            sum += BIT[idx];
            idx -= idx & -idx;  // Move to the parent index
        }

        return sum;
    }

    // Range sum query from index l to r
    int rangeQuery(int l, int r) {
        return query(r) - query(l - 1);
    }
};

int main() {
    vector<int> arr = {1, 2, 3, 4, 5, 6, 7, 8};  // 0-based array
    int n = (int) arr.size();

    FenwickTree fenwickTree(n);

    // Build the Fenwick Tree by updating each element
    for (int i = 1; i <= n; i++) {
        fenwickTree.update(i, arr[i-1]);  // Adjusting 1-based indexing
    }

    // Query the prefix sum up to index 5
    cout << "Sum of first 5 elements: " << fenwickTree.query(5) << endl;

    // Update element at index 7 (1-based index)
    fenwickTree.update(7, 3);  // Increment element at index 7 by 3

    // Query the range sum from index 3 to 7
    cout << "Sum from index 3 to 7 after update: " << fenwickTree.rangeQuery(3, 7) << endl;

    // Update element at index 2 (1-based index)
    fenwickTree.update(2, -2);  // Decrement element at index 2 by 2

    // Query the prefix sum again after the update
    cout << "Sum of first 5 elements after update: " << fenwickTree.query(5) << endl;

    return 0;
}

Output

Sum of first 5 elements: 15
Sum from index 3 to 7 after update: 28
Sum of first 5 elements after update: 13

Explanation of the Code

• update() function updates the Fenwick Tree by adding delta to BIT[idx] and propagating the update to all relevant nodes in O(logn).
• query() function calculates the prefix sum from index 1 to idx in O(logn)
• rangeQuery() function calculates the sum of elements between two indices l and r in O(logn)

Time and Space Complexity Analysis

Time Complexity

Update Operation: O(log⁡n)

The update() function propagates the changes to relevant nodes in the tree. For each index idx, it updates BIT[idx] and then moves to the next index determined by idx = idx + (idx & − idx). This process continues until the index exceeds the size of the array.

In the worst case, the number of updates performed is proportional to the number of 1s in the binary representation of n (the size of the array). The number of 1s in the binary representation of a number n is at most logn, so the update operation takes O(logn) time.

Prefix Sum Query: O(log⁡n)

The query() function computes the prefix sum from index 1 to idx. It works by traversing the tree in reverse, moving from the current index idx to its parent node. Similar to the update operation, the query() function performs at most logn steps, since each step removes one of the lowest set bits in the binary representation of idx. Therefore, the time complexity for the prefix sum query is also O(logn).

Range Sum Query: O(log⁡n)

The rangeQuery() function computes the sum of elements between indices l and r (inclusive) by calling the query() function twice: once for the prefix sum up to r (arr[1]+..+arr[r]) and once for the prefix sum up to l-1 (arr[1]+..+arr[l-1]). Each prefix sum query takes O(logn), so the total time complexity for the range sum query is also O(logn).

Space Complexity

The Fenwick Tree requires an array BIT[] of size n+1, where n is the size of the original array. The extra 1 index is because the Fenwick Tree uses 1-based indexing to simplify operations on the tree. Hence, the space complexity of the Fenwick Tree is O(n).

This is efficient compared to a Segment Tree, which typically requires O(2n) space.

Fenwick Tree can be adapted to handle other range queries beyond sum, as long as the operation you’re working with is associative and can be broken down in a cumulative way (like XOR, GCD, product, etc.). For more complex operations like min/max or non-associative operations, a Segment Tree might be a better fit.

Fenwick Tree is efficient and relatively simple to implement, making it useful in competitive programming and applications involving dynamic sum queries and updates.