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 cumulative frequency tables or prefix sums. It allows both point updates and prefix sum queries to be performed in logarithmic time.

Program Structure

This implementation of a Fenwick Tree in C will include the following components:

1. Functions to initialize the Fenwick Tree.
2. Functions to update the tree with a value at a specific index.
3. Functions to get the prefix sum from the start of the array to a given index.
4. A main function to demonstrate the usage of the Fenwick Tree for point updates and prefix sum queries.

Code Implementation

#include <stdio.h>
#include <stdlib.h>

// Function to update the Fenwick Tree at a specific index
void updateFenwickTree(int fenwickTree[], int n, int index, int value) {
    // Index in Fenwick Tree is 1-based, so increment the index
    index = index + 1;

    // Traverse all ancestors and add 'value'
    while (index <= n) { fenwickTree[index] += value; index += index & (-index); } } // Function to get the prefix sum from the start of the array to a given index int getPrefixSum(int fenwickTree[], int index) { int sum = 0; // Index in Fenwick Tree is 1-based, so increment the index index = index + 1; // Traverse all ancestors and sum the values while (index > 0) {
        sum += fenwickTree[index];
        index -= index & (-index);
    }

    return sum;
}

// Function to construct the Fenwick Tree from a given array
void constructFenwickTree(int arr[], int n, int fenwickTree[]) {
    // Initialize the Fenwick Tree with 0s
    for (int i = 1; i <= n; i++) {
        fenwickTree[i] = 0;
    }

    // Update the Fenwick Tree with values from the input array
    for (int i = 0; i < n; i++) {
        updateFenwickTree(fenwickTree, n, i, arr[i]);
    }
}

// Main function to demonstrate the usage of the Fenwick Tree
int main() {
    int arr[] = {3, 2, -1, 6, 5, 4, -3, 3, 7, 2, 3};
    int n = sizeof(arr) / sizeof(arr[0]);

    // Create a Fenwick Tree array with size n+1 (1-based index)
    int *fenwickTree = (int*)malloc((n + 1) * sizeof(int));

    // Construct the Fenwick Tree
    constructFenwickTree(arr, n, fenwickTree);

    // Output the prefix sums
    printf("Prefix sum of the first 5 elements: %d\n", getPrefixSum(fenwickTree, 4));
    printf("Prefix sum of the first 7 elements: %d\n", getPrefixSum(fenwickTree, 6));
    printf("Prefix sum of the first 10 elements: %d\n", getPrefixSum(fenwickTree, 9));

    // Update the array (for example, arr[3] += 3)
    updateFenwickTree(fenwickTree, n, 3, 3);

    // Output the updated prefix sums
    printf("Updated prefix sum of the first 5 elements: %d\n", getPrefixSum(fenwickTree, 4));
    printf("Updated prefix sum of the first 7 elements: %d\n", getPrefixSum(fenwickTree, 6));
    printf("Updated prefix sum of the first 10 elements: %d\n", getPrefixSum(fenwickTree, 9));

    // Free allocated memory
    free(fenwickTree);

    return 0;
}

Explanation

The program implements a Fenwick Tree (Binary Indexed Tree) in C, which is used to efficiently calculate prefix sums and update elements in a dynamic array. The Fenwick Tree supports both update and query operations in logarithmic time, making it a powerful tool for applications where frequent updates and prefix sum calculations are required.

The key components of this implementation are as follows:

The updateFenwickTree() function updates the Fenwick Tree at a specific index. Since the tree is 1-based, the function increments the index and then traverses all the ancestors of the node, updating their values accordingly.

The getPrefixSum() function calculates the prefix sum from the start of the array to a given index. It traverses the tree by moving up from the given index to its ancestors and summing the values along the way.

The constructFenwickTree() function builds the Fenwick Tree from an input array. It initializes the tree with zeros and then updates it with the values from the array.

In the main() function, we demonstrate the Fenwick Tree’s functionality by creating a tree for an array, calculating prefix sums, performing an update operation, and then recalculating the prefix sums to show the updated results.

This implementation of the Fenwick Tree allows efficient querying and updating of prefix sums, making it useful for tasks such as cumulative frequency tables, range queries, and dynamic prefix sum calculations.