Fenwick Tree (Binary Indexed Tree) Implementation in C++

A Fenwick Tree, also known as a Binary Indexed Tree (BIT), is a data structure that provides efficient methods for calculating and updating prefix sums of a table of values. It is particularly useful for solving problems that involve frequent updates and prefix sum queries on arrays.

Program Structure

The C++ implementation of a Fenwick Tree will include:

1. Fenwick Tree Array: Creating an array to represent the Fenwick Tree structure.
2. Update Operation: Implementing the update function to add a value to an element and propagate the changes in the tree.
3. Prefix Sum Query: Implementing the query function to calculate the prefix sum from the start of the array to a given index.
4. Range Sum Query: Implementing a function to calculate the sum of a range of elements using prefix sums.

Code Implementation

#include <iostream>
#include <vector>

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

public:
    FenwickTree(int size) : n(size) {
        BIT.resize(n + 1, 0);
    }

    // Update function to add value to an element
    void update(int index, int value) {
        index += 1; // BIT uses 1-based indexing
        while (index <= n) { BIT[index] += value; index += index & (-index); // Move to the next index } } // Query function to get prefix sum from 0 to index int query(int index) { index += 1; // BIT uses 1-based indexing int sum = 0; while (index > 0) {
            sum += BIT[index];
            index -= index & (-index); // Move to the parent index
        }
        return sum;
    }

    // Function to get sum of elements in range [left, right]
    int rangeSum(int left, int right) {
        return query(right) - query(left - 1);
    }
};

// Main function to demonstrate the Fenwick Tree operations
int main() {
    std::vector<int> data = {1, 7, 3, 0, 7, 8, 3, 2, 6, 2};
    int n = data.size();

    FenwickTree fenwickTree(n);

    // Build the Fenwick Tree
    for (int i = 0; i < n; i++) {
        fenwickTree.update(i, data[i]);
    }

    // Display prefix sum up to index 5
    std::cout << "Prefix sum up to index 5: " << fenwickTree.query(5) << std::endl;

    // Display sum of elements in range [2, 7]
    std::cout << "Sum of elements in range [2, 7]: " << fenwickTree.rangeSum(2, 7) << std::endl;

    // Update index 3 by adding 5
    fenwickTree.update(3, 5);
    std::cout << "After updating index 3 by adding 5:" << std::endl;

    // Display prefix sum up to index 5 after update
    std::cout << "Prefix sum up to index 5: " << fenwickTree.query(5) << std::endl;

    return 0;
}

Explanation

Fenwick Tree Array

The FenwickTree class contains a vector BIT that represents the Fenwick Tree. The size of this vector is n + 1 because the Fenwick Tree uses 1-based indexing. The size n is initialized in the constructor.

Update Operation

The update() function is used to add a value to an element at a given index in the array. This function updates the Fenwick Tree by adding the value to the corresponding positions and propagating the changes to maintain the tree structure. The index is incremented by 1 to adjust for 1-based indexing, and the loop continues until the end of the tree is reached.

Prefix Sum Query

The query() function calculates the prefix sum from the start of the array up to a given index. It traverses the Fenwick Tree in reverse, summing the relevant elements. The index is decremented by the value of the least significant bit (LSB) until it reaches 0.

Range Sum Query

The rangeSum() function calculates the sum of elements within a given range [left, right]. It does this by subtracting the prefix sum up to left-1 from the prefix sum up to right.

Conclusion

The Fenwick Tree (Binary Indexed Tree) is an efficient data structure for performing prefix sum queries and updates on an array. It provides a time complexity of O(log n) for both operations, making it suitable for scenarios where frequent updates and queries are needed. This C++ implementation covers the essential operations of the Fenwick Tree, including updates, prefix sum queries, and range sum queries.