# Fenwick Tree in Java

### 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.

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.