Fenwick Tree | Binary Indexed Trees

Learn via video course
View all courses
DSA Problem Solving for Interviews using Java
DSA Problem Solving for Interviews using Java
by Jitender Punia
Start Learning
DSA Problem Solving for Interviews using Java
DSA Problem Solving for Interviews using Java
by Jitender Punia
Start Learning
Topics Covered

The Binary Indexed Tree, also known as the Fenwick tree, provides an efficient way to calculate prefix sums of a series of numbers, especially in scenarios where the values are mutable. Unlike prefix sum arrays, which excel in answering prefix sum queries but struggle with frequent updates, Fenwick trees offer a balance between efficient query answering and mutable value updates.

By maintaining cumulative frequencies of array elements at each node, Fenwick trees enable prefix sum calculations in logarithmic time complexity.

Utilizing the concept that any integer will be expressed as the sum of powers of 2, Fenwick trees store the sum of a specific range of elements at an index in the auxiliary array, facilitating quick prefix sum computations with minimal space overhead.

For Example: Prefix Sum

Representation of Fenwick Tree

The BIT (Binary Indexed Tree) is represented as an array (say bitbit). Where each index of bitbit stores the sum of a range of elements of the original array (say aa).

Let ii be an index of the array bitbit, then bit[i]bit[i] will contain the sum of elements KaTeX parse error: $ within math mode where xx is the position of the least significant set-bit in the binary representation of ii. Binary Representation of number

Let us understand by an Example: Let's say we want to know the range of which sum is stored in bit[12]bit[12], we know that binary representation of 1212 is 11001100, we can see that the position of least significant set-bit from right, xx is 33.

That means bit[12]bit[12] will contain the sum of the range (13231+1)12(13-2^{3-1}+1) \rightarrow 12 i.e.i.e. 9129 \rightarrow 12.

Different Ranges of bits

The above image represents the range of elements for which the sum is stored for any index i in the bit array of size 16.

For Example: index 12 in bit holds the sum of the values of the range [912][9\rightarrow 12] present in a and index 8 in bit holds the sum of the values of the range [18][1\rightarrow 8] in a. So to find the prefix_sum[12] we can simply find bit[12]+bit[8]bit[12]+bit[8] instead of calculating sum one by one.

Construction of Fenwick Tree

Let's say we have been given an array aa, of size nn. So we will create another array of size n+1n+1(say bitbit) all of its entries will be initialized with 0. Then we will use the update function for each index of array aa. Its pseudocode will be like -

For Example: Let a={4,2,1,5,6,3,9,7,2,3}a=\{4,2,1,5,6,3,9,7,2,3\} Then bitbit array will correspond to - {4,6,1,12,6,9,9,37,2,5}\{4,6,1,12,6,9,9 ,37,2,5 \} where bit[i]bit[i] represents sum of range (i2x1+1)i(i-2^{x-1}+1) \rightarrow i

Operations of Fenwick Tree

The two main operations supported by Fewick tree are -

  • getSum(x) - This operation returns the sum of first xx elements of the array i.e.i.e. a[0]+a[1]+...+a[x]a[0]+a[1]+...+a[x].
  • update(x,val) - This operation updates the value of aa at index xx i.e.i.e. a[x]=vala[x]=val

Different Operations of Fenwick Tree

We can also find the sum of any arbitrary range [left,right][left,right] using the below-given function which uses getSum(x) to find the same.

getSumRange(left, right): This operation returns the sum of array elements within a range i.e.i.e. a[left]+a[left+1]+...+a[right]a[left]+a[left+1]+...+a[right]. It can be easily calculated using _getSum(x)_ operation by returning getSum(right+1)-getSum(left)

How does Binary Indexed Tree work?

The core idea revolves around leveraging the property that any positive integer can be expressed into a sum of powers of 2.

For instance, take the number 15, which can be expressed as 8 + 4 + 2 + 1. Within the Binary Indexed Tree (BIT), each node aggregates the sum of a distinct range of elements. The range of elements represented by each node in the Binary Indexed Tree (BIT) is determined by the position of the least significant set bit in its binary index. Consider an example where we need to calculate the sum of the first 15 elements. To achieve this, we sum the last 8 elements (from 8 to 15) along with the sum of the preceding 4 elements (from 4 to 7) and the initial 2 elements (from 2 to 3). As the number of set bits in a number's binary representation is O(Logn), both getSum() and update() operations traverse at most O(Logn) nodes. Building the Binary Indexed Tree (BIT) requires O(nLogn) time complexity since it invokes the update() function for each of the n elements.

getSum(x) operation:

getSum(x) operation returns sum of array elements from 0th0^{th} index to xthx^{th} index i.e.i.e. a[0]+a[1]+...+a[x]a[0]+a[1]+...+a[x]. Steps invloved to calculate it are -

  • Initialize answer, ans with 0.
  • Increase x by 1 (To maintain 1-based indexing).
  • While x is greater than 0
    • ans+=bit[x]ans+=bit[x]
    • x=(x&(x))x-=(x\&(-x))
  • Move to the parent of the BITree[index] by eliminating the rightmost set bit from the current index. i.e. x=(x&(x))x-=(x\&(-x)).
  • Return ans

update(x, val) operation

update(x, val) operation updates the value of array aa at index xx to valval. After updating, we also need to update bitbit array at those indices which get impacted by the element at index xx. , Steps involved in that are -

  • Find the change happening at the index x, δval=vala[x]\delta val=val-a[x].
  • Update the value at index x i.e.i.e. a[x]=vala[x]=val.
  • While xnx\leq n
    • bit[x]+=δvalbit[x]+=\delta val
    • x+=(x&(x))x+=(x\&(-x))
  • Move to the next element of BITree[index] by incrementing the rightmost set bit of the current index. i.e. x+=(x&(x))x+=(x\&(-x)).

Code Implementation

To implement the Fenwick tree (BIT) we will have the following global variables to maintain simplicity in the code.

  • n- It denotes the size of the array on which we want to perform certain operations which are discussed in the previous sections.
  • bit- It is the actual binary indexed tree that is represented in array format. Its size will be n+1 to maintain 1-based indexing.

The functions which are needed to implement functionalities of the binary indexed trees are :

  • FindSum- It takes one argument (say ind) and we need to return the sum of values of the given array (say a) in the range [0, ind].
  • SumOfRange- It takes two arguments (say left and right) and we will return the sum of values of a in the range [left, right]
  • Update- It takes two arguments (sat ind and val) and we need to change the value of a at index ind to val and correspondingly we also need to update the bit.




Output: Sum of range 2-6 is 24. Sum of range 5-9 is 33.

Complexity Analysis of Fenwick Tree

  • Time Complexity:
    • Construction: O(n * log n)
    • Query: O(log n)
    • Update: O(log n)

This is because the number of nodes visited is proportional to the number of set bits in the binary representation of the index.

  • Space Complexity:
    • O(n)

Applications of Fenwick Tree

Fenwick Tree is mainly used to optimize the process of finding the prefix sum of the arrays such that we can have the prefix sum of an array index in logarithmic time complexity. However, there are some popular questions that can be efficiently solved using Fenwick trees:

  • Mutable Range Sum Queries: Q queries can be answered in O(Q×logn)O(Q\times \log{n}) time which is way better than O(Q×N)O(Q\times N) run-time of brute force approach.
  • Count Inversions in an Array: The number of inversions can easily be found in O(n×logn)O(n\times \log{n}) time even without sorting the array.
  • Count smaller numbers after self: Many practical uses can be seen in the real world which can be computed efficiently using BIT.


  • Binary Indexed Tree (Fenwick Tree) is an efficient data structure that can be used to quickly calculate the prefix sum of an array.
  • If the values present in the array are mutable i.e.i.e. values can be changed using the Fenwick tree is of great use.
  • Subtracting x&(x)x\&(-x) from xx, is the efficient way to remove the least significant set-bit from xx.
  • Time Complexity to calculate prefix sum or range sum of the array of size nn is O(log(n))O(log(n)) and O(n)O(n) extra space is required to store the bitbit array.