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

Malay Gain
0 upvote

## 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.

## 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) )

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

Complexity

updateBIT takes O(log n) time in the worst case where n is the size of the given array.

Output

## 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!

Live masterclass