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.
Let’s see the representation of the Binary Indexed Tree.
Representation
Binary Indexed Tree is represented as an array. For any given array of integers, we can store the sum of some integers of the given array at any index of the Binary Indexed Tree array.
As any integer can be represented as the sum of powers of 2 ( i.e., the concept of binary representation). So, for any index of a binary indexed tree array, we can find a range of indices whose summation can be stored at that index.
BIT[ ] is a 1-indexed array(the representation of the Binary Indexed Tree for the given array)
1= 0 + 20 ;start index=0, end index=0
BIT[1]= arr[0]
2=0 + 21;start index=0, end index=1
BIT[1]= arr[0]+ arr[1]
3=21 + 20;start index=2, end index=2
BIT[3]= arr[2]
7=22+ 21 + 20 =6 + 20;start index=6, end index=6
BIT[7]= arr[6]
Similarly, we can get the range of indices for each index of the BIT[ ] array.
The range of each node of the binary index tree is mentioned beside the node.
In the above diagram, the summation of the corresponding ranges is stored in the node.
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.
int prefixSum(int BIT[], int index) { int sum = 0; // indexin BIT[] is1 more than the indexin arr[] index = index + 1; // Traverse ancestors of BIT[index] while (index>0) { // adding current element of BIT[] tosum sum += BIT[index]; // moving current indexto 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 tonext 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++ code for implementation of Binary Index Tree #include <iostream> usingnamespacestd; /* 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
voidupdateBIT(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 = newint[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[]
intprefixSum(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 intmain() { 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); return0; }
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.
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.
2). Difference between binary indexed tree and segment tree?
The binary indexed tree takes less space than the segment tree, and its implementation is relatively easier than a segment tree.
3). Application of binary indexed tree?
Binary indexed tree is used to count inversions in an array and to implement arithmetic coding algorithms.
Key Takeaways
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.
Apart from this, you can practice a wide range of coding questions commonly asked in interviews in Coding Ninjas Studio. Along with coding questions, we can also find the interview experience of scholars working in renowned product-based companies here.
38+ registered 