Fenwick Tree (Binary Indexed Tree) Implementation in Java

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 in a table of numbers. It allows for queries and updates in logarithmic time, making it very useful for tasks like cumulative frequency tables.

Program Structure

The implementation of a Fenwick Tree involves a single class:

• FenwickTree: Manages the creation, update, and querying of the prefix sums.

FenwickTree Class

This class encapsulates the functionality of the Fenwick Tree. The class contains the following components:

• Constructor: Initializes the Fenwick Tree with a given size.
• update: Updates the Fenwick Tree with a value at a specific index.
• query: Retrieves the prefix sum up to a specified index.
• rangeQuery: Retrieves the sum of elements between two indices (inclusive).

Java Code Implementation

FenwickTree Class


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

public FenwickTree(int size) {
n = size;
tree = new int[n + 1];
}

public void update(int index, int delta) {
index++; // Convert to 1-based index
while (index <= n) {
tree[index] += delta;
index += index & -index; // Move to the next index
}
}

public int query(int index) {
index++; // Convert to 1-based index
int sum = 0;
while (index > 0) {
sum += tree[index];
index -= index & -index; // Move to the parent index
}
return sum;
}

public int rangeQuery(int left, int right) {
return query(right) – query(left – 1);
}
}

Explanation

Here is a detailed explanation of the key components in the FenwickTree class:

1. Constructor

The constructor initializes the Fenwick Tree for a given size. The tree is represented by an integer array of size n + 1, where n is the number of elements in the original array. The extra element is used to accommodate 1-based indexing, which simplifies the implementation.

2. update Method

This method updates the Fenwick Tree by adding a value delta at a specific index. The update is propagated up the tree by iterating over the relevant indices, using the formula index += index & -index to move to the next node in the tree. This ensures that the prefix sums are updated efficiently.

3. query Method

The query method returns the prefix sum up to a specified index. It works by summing the values of the relevant nodes, moving up the tree with the formula index -= index & -index to get to the parent nodes. The result is the sum of elements from the start of the array up to the given index.

4. rangeQuery Method

This method computes the sum of elements between two indices (inclusive). It does so by taking the difference between the prefix sum up to the right index and the prefix sum up to left - 1. This allows for efficient range sum queries.

Conclusion

This Fenwick Tree (Binary Indexed Tree) implementation in Java allows for efficient prefix sum calculations and updates. The data structure is especially useful for scenarios where you need to frequently update elements in an array and query prefix sums or range sums.