Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Representation
3.
Operations
4.
Code
5.
Complexity analysis
6.
FAQs
7.
Key Takeaways
Last Updated: Mar 27, 2024

Binary Indexed Tree or Fenwick Tree

Author Malay Gain
0 upvote
Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

Introduction

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.

 

Let’s visualize this through an example.

 

Given array arr = [3, 2, - 4, 5, 7, 3, - 2, 4, 7, 1, 3, 5, 1, 6, - 2]

 

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.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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 sum0;
 
    // index in BIT[] is 1 more than the index in arr[]
    indexindex1;
 
    // 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++ 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.
intconstructBITree(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[] = {32-4573-24713516-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;
}

 

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

FAQs

 

1). 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.

 

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.

Recommended problems -

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. 

Happy learning!

 

 

Previous article
Two Dimensional Fenwick Tree
Next article
Binary Indexed Tree or Fenwick Tree
Live masterclass