Fenwick Tree in Java

Introduction:

What is a Fenwick Tree?

Fenwick Tree, also known as Binary Indexed Tree, is a data structure that allows efficient querying and updating of prefix sums of an array. It was invented by Peter Fenwick in 1994 and has since become an essential tool in solving problems related to cumulative frequency counting.

The Fenwick tree is a binary tree that is used to store partial sums of an array. The leaf nodes of the tree correspond to the elements of the array, and the parent nodes store the sum of their children. The structure of the tree is such that the path from the root to a leaf node represents a prefix of the array.

Scenario where it is used:

Suppose you have an array of N integers, and you want to compute the sum of all elements in a subarray between indices l and r, inclusive. A naive approach would be to iterate over the subarray and add up all the elements. However, this approach would have a time complexity of O(N) for each query, which can be slow for large arrays or frequent queries.

To improve the performance, you can use a Fenwick tree to represent the array. The tree is initialized with the original values of the array, and each node of the tree stores the sum of a range of elements in the array. The tree is constructed in O(N log N) time complexity.

To compute the sum of a subarray, you can use the sum operation of the Fenwick tree. The sum operation involves traversing the tree and adding up the values of the nodes that correspond to the subarray. Though the operation has a time complexity of O(log N).

Let us consider an array:

[3, 1, 4, 2, 8, 5, 7, 6]

We can construct a Fenwick Tree for this array as follows:

[0, 0, 0, 0, 0, 0, 0, 0, 0]

[1, 0, 0, 0, 0, 0, 0, 0, 0]   # update index 1 with a value of 1

[1, 0, 1, 0, 0, 0, 0, 0, 0]   # update index 3 with a value of 1

[1, 1, 1, 0, 0, 0, 0, 0, 0]   # update index 2 with a value of 1

[1, 1, 1, 1, 0, 0, 0, 0, 0]   # update index 4 with a value of 1

[1, 1, 1, 1, 0, 1, 0, 0, 0]   # update index 6 with a value of 1

[1, 1, 1, 1, 0, 1, 1, 0, 0]   # update index 7 with a value of 1

[1, 1, 1, 1, 0, 1, 1, 1, 0]   # update index 8 with a value of 1

[1, 1, 1, 1, 1, 1, 1, 1, 0]   # update index 5 with a value of 1

To compute the number of elements in the array that are less than or equal to 5, we perform a range query from index 1 to index 5 and get a result of 5. It tells us that there are 5 elements in the array that are less than or equal to 5.

Implementation:

Fenwick Tree can be implemented as an array of integers, where each element in the array represents the cumulative sum of a range of elements in the input array. The size of the array is usually set to n+1, where n is the size of the input array. The reason for this is that Fenwick Tree is a 1-indexed data structure, meaning that the first element in the array is not used.

Program:

FileName: FenwickTree.java

import java.util.Arrays;


public class FenwickTree {
    int[] tree;


    public FenwickTree(int n) {
        this.tree = new int[n+1];  // initialize the tree with all zeros
    }


    // update the Fenwick Tree with a delta value at a specific index
    public void update(int index, int delta) {
        while(index < tree.length) {  // loop through the tree
            tree[index] += delta;  // add delta to the current element
            index += index & -index;  // update the index to move to the parent node
        }
    }


    // compute the cumulative sum from the first element to a specific index
    public int query(int index) {
        int sum = 0;
        while(index > 0) {  // loop through the tree
            sum += tree[index];  // add the current element to the sum
            index -= index & -index;  // update the index to move to the previous node
        }
        return sum;
    }


    public static void main(String[] args) {
        int[] inputArray = {1, 3, 5, 7, 9, 11};


        FenwickTree tree = new FenwickTree(inputArray.length);


        // construct the Fenwick Tree by updating each element in the tree with the corresponding value from the input array
        for(int i = 0; i < inputArray.length; i++) {
            tree.update(i+1, inputArray[i]);
        }


        // print the constructed Fenwick Tree
        System.out.println("Constructed Fenwick Tree: " + Arrays.toString(tree.tree));


        // perform range queries
        int sum1 = tree.query(3);    // returns 9
        int sum2 = tree.query(6);    // returns 36


        // print the results of the range queries
        System.out.println("Query 1: " + sum1);
        System.out.println("Query 2: " + sum2);
    }
}

Output:

Constructed Fenwick Tree: [0, 1, 4, 5, 15, 9, 20]
Query 1: 9
Query 2: 36

Explanation:

In this implementation, the FenwickTree class has two methods: update and query, which are used to update the tree and perform range queries, respectively. The main method is used to demonstrate the construction of the Fenwick Tree and the performance of range queries on the tree.

Complexity Analysis:

• Time Complexity:
  The time complexity of constructing a Fenwick tree is O(N log N), where N is the size of the array because we need to perform N update operations, each taking O(log N) time, to initialize the tree.
  
  The time complexity of computing the sum of elements in a subarray using a Fenwick tree is O(log N), where N is the size of the array because the sum operation involves traversing the tree from the leaf node corresponding to the starting index of the subarray to the root node, with each step taking O(1) time.
  
  Therefore the overall time complexity of above program is O(NlogN)

• Space Complexity: The space complexity of a Fenwick tree is O(N), where N is the size of the array because we need to store the tree array, which has N + 1 elements, where the first element is always 0 and the remaining N elements correspond to the original array.

Advantages of Fenwick tree:

1. Efficient range queries: Fenwick trees can efficiently compute the sum of elements in a subarray or update a range of elements in logarithmic time complexity. Which makes them useful in scenarios where we need to perform many range queries or updates.
2. Space efficiency: Fenwick trees require O(N) space complexity to store the original array and the tree. It is more space-efficient than other data structures like segment trees, which require O(4N) space complexity.
3. Easy to implement: Implementing a Fenwick tree is relatively straightforward, and the code can be concise and efficient.

Disadvantages of  Fenwick tree:

1. Limited functionality: Fenwick trees are specialized data structures that are designed for a specific type of query, namely range queries on a one-dimensional array. They are not as versatile as other data structures like segment trees, which can perform a wide variety of operations on different types of data.
2. Complexity: Although the concept behind Fenwick trees is relatively simple, their implementation can be tricky, especially for beginners. The tree operations require bit manipulation, which can be unintuitive for some developers.
3. Not always optimal: Fenwick trees can be an efficient data structure for range queries, but they may not always be the optimal choice for every scenario. For example, if the range queries involve multiple dimensions or more complex operations, other data structures may be more appropriate.

Applications:

1. Finding the frequency of elements in an array: Fenwick trees can be used to efficiently compute the frequency of each element in an array. This can be useful for many applications, such as finding the most common element in an array.
2. Computing inversions in an array: Fenwick trees can be used to efficiently compute the number of inversions in an array. This can be useful for applications such as sorting and ranking items based on their position in an array.
3. Solving geometric problems: Fenwick trees can be used to efficiently solve a wide range of geometric problems, such as finding the number of points in a given region or computing the centroid of a set of points.
4. Dynamic programming: Fenwick trees can be used in dynamic programming algorithms to efficiently compute the value of a function over a range of values. This can be useful for many types of problems, such as finding the shortest path between two points in a graph or computing the optimal placement of items in a knapsack.