Fenwick Tree or, Binary Indexed Tree

Fenwick tree also known as Binary Indexed Tree (BIT) is a data structure that is designed for querying and updating the prefix sums of an array efficiently.

Fenwick trees permit both operations to be accomplished in O(log m) time. This is obtained by representing the numbers as a tree, where the value of each node is treated as the sum of the numbers in that subtree. The tree structure permits operations to be accomplished using only O(log m) node accesses.

For example, you are tracking customer reward points for each day on basis of the number of orders placed. You need to calculate the total reward points for a range of days.

You want to quickly check their total points up to a specific day and update the points for a specific day. Here, you can use Fenwick tree to calculate the cumulative sum of the reward points in a range of days.

Characteristics of Fenwick Tree

Following are the characteristics of Fenwick tree:

• Size : The size of the Fenwick tree is equal to the size of the input array.
• Height : The height of the Fenwick tree is O(log n).
• Parent : The parent of the ith node is i - (i & -i).
• Child : The child of the ith node is i + (i & -i).

Structure of Fenwick Tree

Fenwick tree is a binary tree that is represented as an array. It is implemented as a one-dimensional array where each element stores information about a segment of the original array.

It uses binary indexing for showing cumulative data.

• Indexing starts from 1 for making it simple, though 0-based can be used.
• Each index in Fenwick tree array shows a specific range of the original array.

Operation on Fenwick Tree

There are basically two main operations that can be performed on Fenwick tree:

• Query : It is used to find the sum of the elements from the start of the array to a specific index.
• Update : It is used to update the value of an element in the array.

Query Operation on Fenwick Tree

We will find the sum of the elements from the start of the array to a specific index. This example will help you understand the query operation on Fenwick tree.

In order to perform the query operation on Fenwick tree, all you need to do is follow the steps below:

1. Initialize the sum as 0.
2. Traverse the Fenwick tree from the given index to 1.
3. Add the value of the current index to the sum.
4. Update the index to the parent of the current index.
5. Repeat the above steps until the index is greater than 0.
6. Return the sum.

Code for Query Operation

Following is the code for the query operation on Fenwick tree in C, C++, Java, and Python:

#include <stdio.h>

// Function to update Fenwick Tree
void update(int *fenwickTree, int n, int index, int value) {
   while (index <= n) {
      fenwickTree[index] += value;
      index += index & -index;  // Move to next index
   }
}

// Function to find the sum from index 1 to a given index
int query(int *fenwickTree, int index) {
   int sum = 0;
   while (index > 0) {
      sum += fenwickTree[index];
      index -= index & -index;  // Move to parent index
   }
   return sum;
}

int main() {
   int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
   int n = sizeof(arr) / sizeof(arr[0]);

   int fenwickTree[n + 1];  // Fenwick Tree (1-based index)
   
   // Initialize Fenwick Tree with 0
   for (int i = 0; i <= n; i++) {
      fenwickTree[i] = 0;
   }

   // Build the Fenwick Tree
   for (int i = 0; i < n; i++) {
      update(fenwickTree, n, i + 1, arr[i]);  // Update with arr[i]
   }

   // Query sums
   printf("Sum of elements from 1 to 5: %d\n", query(fenwickTree, 5));
   printf("Sum of elements from 1 to 10: %d\n", query(fenwickTree, 10));

   return 0;
}

Sum of elements from 1 to 5: 15
Sum of elements from 1 to 10: 55

// C++ program to demonstrate the query operation on Fenwick tree
#include <iostream>
using namespace std;

// Function to update Fenwick Tree
void update(int *fenwickTree, int n, int index, int value) {
   while (index <= n) {
      fenwickTree[index] += value;
      index += index & -index;  // Move to next index
   }
}

// Function to find the sum from index 1 to a given index
int query(int *fenwickTree, int index) {
   int sum = 0;
   while (index > 0) {
      sum += fenwickTree[index];
      index -= index & -index;  // Move to parent index
   }
   return sum;
}

int main() {
   int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
   int n = sizeof(arr) / sizeof(arr[0]);

   int fenwickTree[n + 1];  // Fenwick Tree (1-based index)
   
   // Initialize Fenwick Tree with 0
   for (int i = 0; i <= n; i++) {
      fenwickTree[i] = 0;
   }

   // Build the Fenwick Tree
   for (int i = 0; i < n; i++) {
      update(fenwickTree, n, i + 1, arr[i]);  // Update with arr[i]
   }

   // Query sums
   cout << "Sum of elements from 1 to 5: " << query(fenwickTree, 5) << endl;
   cout << "Sum of elements from 1 to 10: " << query(fenwickTree, 10) << endl;

   return 0;
}

Sum of elements from 1 to 5: 15
Sum of elements from 1 to 10: 55

// Java program to demonstrate the query operation on Fenwick tree
public class FenwickTree {
   private int[] fenwickTree;
   private int size;

   // Constructor to initialize Fenwick Tree
   public FenwickTree(int[] arr) {
      this.size = arr.length;
      this.fenwickTree = new int[size + 1];

      // Build the Fenwick Tree
      for (int i = 0; i < size; i++) {
         update(i + 1, arr[i]); // 1-based index
      }
   }

   // Function to update Fenwick Tree
   public void update(int index, int value) {
      while (index <= size) {
         fenwickTree[index] += value;
         index += index & -index; // Move to next index
      }
   }

   // Function to get the prefix sum from 1 to index
   public int query(int index) {
      int sum = 0;
      while (index > 0) {
         sum += fenwickTree[index];
         index -= index & -index; // Move to parent index
      }
      return sum;
   }

   public static void main(String[] args) {
      int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
      FenwickTree fenwickTree = new FenwickTree(arr);

      System.out.println("Sum of elements from 1 to 5: " + fenwickTree.query(5));
      System.out.println("Sum of elements from 1 to 10: " + fenwickTree.query(10));
   }
}

Sum of elements from 1 to 5: 15
Sum of elements from 1 to 10: 55

# Python program to demonstrate the query operation on Fenwick tree

# Function to update Fenwick Tree
def update(fenwickTree, index, value):
   while index <= n:
      fenwickTree[index] += value
      index += index & -index  # Move to next index

# Function to find the sum from index 1 to a given index
def query(fenwickTree, index):
   sum = 0
   while index > 0:
      sum += fenwickTree[index]
      index -= index & -index  # Move to parent index
   return sum

if __name__ == "__main__":
   arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
   n = len(arr)
   fenwickTree = [0] * (n + 1)  # Fenwick Tree (1-based index)

   # Build the Fenwick Tree
   for i in range(n):
      update(fenwickTree, i + 1, arr[i])  # Update with arr[i]

   # Query sums
   print("Sum of elements from 1 to 5:", query(fenwickTree, 5))
   print("Sum of elements from 1 to 10:", query(fenwickTree, 10))

Sum of elements from 1 to 5: 15
Sum of elements from 1 to 10: 55

Update Operation on Fenwick Tree

We will update the value of an element in the array. This example will help you understand the update operation on Fenwick tree.

We need to use the update operation when we need to change the dynamic values of the array. For example, you are tracking customer reward points for each day on the basis of the number of orders placed. You need to update the points for a specific day. Here, you can use the update operation on Fenwick tree to update the points for a specific day.

Follow the steps below to perform the update operation on Fenwick tree:

1. Traverse the Fenwick tree from the given index to the end of the array.
2. Update the value of the current index by adding the value to be updated.
3. Update the index to the child of the current index.
4. Repeat the above steps until the index is less than or equal to the size of the array.

Code for Update Operation

Following is the code for the update operation on Fenwick tree in C, C++, Java, and Python:

// C program to demonstrate the update operation on Fenwick tree
#include <stdio.h>

// Function to update the value of an element in the array
void update(int *fenwickTree, int index, int value, int n){
   while(index <= n){
      fenwickTree[index] += value;
      index += index & -index;
   }
}
// query function
int query(int *fenwickTree, int index){
   int sum = 0;
   while(index > 0){
      sum += fenwickTree[index];
      index -= index & -index;
   }
   return sum;
}
// Main function
int main(){
   int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
   int n = sizeof(arr)/sizeof(arr[0]);
   int fenwickTree[n+1];
   for(int i = 1; i <= n; i++){
      fenwickTree[i] = 0;
   }
   for(int i = 0; i < n; i++){
      int index = i + 1;
      while(index <= n){
         fenwickTree[index] += arr[i];
         index += index & -index;
      }
   }
   update(fenwickTree, 5, 10, n);
   printf("Sum of elements from 1 to 10 after update: %d\n", query(fenwickTree, 10));
   return 0;
}

Sum of elements from 1 to 10 after update: 65

// C++ program to demonstrate the update operation on Fenwick tree
#include <iostream>
using namespace std;

// Function to update the value of an element in the array
void update(int *fenwickTree, int index, int value, int n){
   while(index <= n){
      fenwickTree[index] += value;
      index += index & -index;
   }
}

// query function
int query(int *fenwickTree, int index){
   int sum = 0;
   while(index > 0){
      sum += fenwickTree[index];
      index -= index & -index;
   }
   return sum;
}
// Main function`
int main(){
   int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
   int n = sizeof(arr)/sizeof(arr[0]);
   int fenwickTree[n+1];
   for(int i = 1; i <= n; i++){
      fenwickTree[i] = 0;
   }
   for(int i = 0; i < n; i++){
      int index = i + 1;
      while(index <= n){
         fenwickTree[index] += arr[i];
         index += index & -index;
      }
   }
   update(fenwickTree, 5, 10, n);
   cout << "Sum of elements from 1 to 10 after update: " << query(fenwickTree, 10) << endl;
   return 0;
}

Sum of elements from 1 to 10 after update: 65

// Java program to demonstrate the update operation on Fenwick tree
public class FenwickTree{

// Function to update the value of an element in the array
static void update(int[] fenwickTree, int index, int value, int n){
   while(index <= n){
      fenwickTree[index] += value;
      index += index & -index;
   }
}

// query function
static int query(int[] fenwickTree, int index){
   int sum = 0;
   while(index > 0){
      sum += fenwickTree[index];
      index -= index & -index;
   }
   return sum;
}
// Main function
   public static void main(String[] args){
      int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
      int n = arr.length;
      int[] fenwickTree = new int[n+1];
      for(int i = 1; i <= n; i++){
         fenwickTree[i] = 0;
      }
      for(int i = 0; i < n; i++){
         int index = i + 1;
         while(index <= n){
            fenwickTree[index] += arr[i];
            index += index & -index;
         }
      }
      update(fenwickTree, 5, 10, n);
      System.out.println("Sum of elements from 1 to 10 after update: " + query(fenwickTree, 10));
   }
}

Sum of elements from 1 to 10 after update: 65

# Python program to demonstrate the update operation on Fenwick tree
# Function to update the value of an element in the array
def update(fenwickTree, index, value, n):
   while index <= n:
      fenwickTree[index] += value
      index += index & -index

#query function
def query(fenwickTree, index):
   sum = 0
   while index > 0:
      sum += fenwickTree[index]
      index -= index & -index
   return sum

# Main function
if __name__ == "__main__":
   arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
   n = len(arr)
   fenwickTree = [0] * (n+1)
   for i in range(n):
      index = i + 1
      while index <= n:
         fenwickTree[index] += arr[i]
         index += index & -index
   update(fenwickTree, 5, 10, n)
   print("Sum of elements from 1 to 10 after update:", query(fenwickTree, 10))

Sum of elements from 1 to 10 after update: 65

Applications of Fenwick Tree

Following are the applications of Fenwick tree:

• It is used in computing the prefix sum of an array.
• Also used in inversion count of an array.
• And, it is useful in computing the range sum of an array.

Complexity of Fenwick Tree

Following is the complexity of Fenwick tree:

• Time Complexity : The time complexity of Fenwick tree is O(log n) for both query and update operations.
• Space Complexity : The space complexity of Fenwick tree is O(n).

Conclusion

In this chapter, we learned about what is Fenwick tree, its characteristics, structure, operations, and applications. We also saw how to perform query and update operations on Fenwick tree using code examples in C, C++, Java, and Python. Fenwick tree is a powerful data structure that allows us to efficiently calculate the prefix sum of an array and perform range queries and updates.