Operations
Range sum
The Sum of elements in the array from the index, [ l to r ], can be calculated using the binary indexed tree representation(i.e., BIT[ ]) of the given array.
sum(l, r) = prefixSum(r) - prefixSum(l-1)
For example
To get the prefix sum of any index, i.e., prefixSum(i), we need to follow the below steps:
- As BIT[ ] is a 1-indexed array, we need to start from (i+1)th index of BIT[ ].
- Take a variable, ‘sum,’ to store the prefix sum and initialize it as 0.
- While the index is greater than 0, do the following.
- Add BIT[index ] to sum and move to the parent node of BIT[index ].
- The parent index can be obtained by removing the rightmost set bit of the current index.
parent index=index - (index & 2’s complement(index) )
int prefixSum(int BIT[], int index)
{
int sum = 0;
// index in BIT[] is 1 more than the index in arr[]
index = index + 1;
// Traverse ancestors of BIT[index]
while (index>0)
{
// adding current element of BIT[] to sum
sum += BIT[index];
// moving current index to parent node
index -= index & (-index);
}
return sum;
}
Complexity
prefixSum takes O(log n) time in the worst case where n is the size of the given array.
Update
For any update at a particular index in the given array, we need to update all the nodes that contain the element of that index in the corresponding binary indexed tree.
For example
Steps to be followed to update ith index of the given array with value x:
- we need to add the difference, diff= x - arr[i] while updating BIT[ ] .
- As BIT[ ] is 1-indexed array, we need to start from (i+1)th index of BIT[ ].So, initialize i as i+1;
- While current index i is smaller than equal to the size of the array n, do the following.
- Add the difference, diff to BIT[i] and move to the next index incrementing the last set bit of current index i.
i = i + (i + (i & 2’s complement(i))
void updateBIT(int BITree[], int n, int i, int diff)
{
// index in BIT[] is 1 more than the index in arr[]
i = i + 1;
// traversing all ancestors and adding 'diff'
while (i <= n)
{
// adding 'diff' to current node of binary indexed tree
BITree[i] += diff;
// moving index to next index where value needs to be updated
i += i & (-i);
}
}
Complexity
updateBIT takes O(log n) time in the worst case where n is the size of the given array.
Code
C++
// C++ code for implementation of Binary Index Tree
#include <iostream>
using namespace std;
/* arr[0..n-1] --> input array for which prefix sum is evaluated.
BIT[0..n] --> array that represents Binary Indexed Tree. */
// function for updating the binary indexed tree
void updateBIT(int BITree[], int n, int i, int diff)
{
// index in BIT[] is 1 more than the index in arr[]
i = i + 1;
// traversing all ancestors and adding 'diff'
while (i <= n)
{
// adding 'diff' to current node of binary indexed tree
BITree[i] += diff;
// moving index to next index where value need to be updated
i += i & (-i);
}
}
// constructing a Binary Indexed Tree for given
// array of size n.
int* constructBITree(int arr[], int n)
{
// initializing BIT[] as 0
int *BIT = new int[n+1];
for (int i=1; i<=n; i++)
BIT[i] = 0;
// storing the actual values of arr[] in BIT[] using update()
for (int i=0; i<n; i++)
updateBIT(BIT, n, i, arr[i]);
return BIT;
}
// partial sums of array elements are stored in BIT[]
int prefixSum(int BIT[], int index)
{
int sum = 0;
// index in BIT[] is 1 more than the index in arr[]
index = index + 1;
// Traverse ancestors of BIT[index]
while (index>0)
{
// adding current element of BIT[] to sum
sum += BIT[index];
// moving current index to parent node
index -= index & (-index);
}
return sum;
}
// Driver code
int main()
{
int arr[] = {3, 2, -4, 5, 7, 3, -2, 4, 7, 1, 3, 5, 1, 6, -2};
int n = sizeof(arr)/sizeof(arr[0]);
int *BITree = constructBITree(arr, n);
cout << "Sum of elements in arr[0..6] is "<< prefixSum(BITree, 6);
// updating the value of index 3 to 6
int diff=8 - arr[3];
arr[3] += diff;
updateBIT(BITree, n, 3, diff); //Update BIT for above change in arr[]
cout << "\nSum of elements in arr[0..6] after update is " << prefixSum(BITree, 6);
return 0;
}
You can also try this code with Online C++ Compiler
Output
Sum of elements in arr[0..6] is 14
Sum of elements in arr[0..6] after update is 17
Complexity analysis
Complexity for constructing binary indexed trees is O(n logn) in the worst case as it uses the updateBIT() function which takes O(log n) time in the worst case where n is the size of the given array.
Space complexity is O(n) for constructing binary indexed trees.
Check out this problem - Count Inversions
Frequently Asked Questions
What is the binary indexed tree?
Binary Indexed Tree or Fenwick Tree is a special kind of data structure to calculate the sum of a given range of an array and update the array efficiently for a large number of queries.
What is the use case of Binary Indexed Tree?
Binary Indexed Tree efficiently handles dynamic prefix sum calculations and point updates, making it ideal for range queries in competitive programming and data analysis.
What is indexing a binary search tree?
Indexing a Binary Search Tree involves assigning sequential indices to nodes for easy navigation or referencing, often used in in-order traversal or storage schemes.
Conclusion
This article covered the Binary Indexed Tree or Fenwick Tree. We have learned about the application of the binary indexed tree to solve problems like the range sum or prefix sum of an array efficiently.
Recommended problems -
Apart from this, you can practice a wide range of coding questions commonly asked in interviews in Code360. Along with coding questions, we can also find the interview experience of scholars working in renowned product-based companies here.
84+ registered