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 Treevoidupdate(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 indexintquery(int*fenwickTree,int index){int sum =0;while(index >0){
sum += fenwickTree[index];
index -= index &-index;// Move to parent index}return sum;}intmain(){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 0for(int i =0; i <= n; i++){
fenwickTree[i]=0;}// Build the Fenwick Treefor(int i =0; i < n; i++){update(fenwickTree, n, i +1, arr[i]);// Update with arr[i]}// Query sumsprintf("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));return0;}
Output
Following is the output of the above code:
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 arrayvoidupdate(int*fenwickTree,int index,int value,int n){while(index <= n){
fenwickTree[index]+= value;
index += index &-index;}}// query functionintquery(int*fenwickTree,int index){int sum =0;while(index >0){
sum += fenwickTree[index];
index -= index &-index;}return sum;}// Main functionintmain(){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));return0;}
Output
Following is the output of the above code:
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.
Leave a Reply