Binary Indexed Tree or Fenwick Tree

Sample Test Cases

Input:   

8
9 2 1 5 11 0 2 4
4
1 4
0 3 2
1 4
1 8

Output: 

17
 18
 35

Explanation: 

(1, 4): The sum of the first four elements is 9 + 2 + 1 + 5 = 17.
(0, 3, 2): Update the value at index 3 with element 2, so the new array is 9 2 2 5 11 0 2 4.
(1, 4): Now the sum of the first four elements is 9 + 2 + 2 + 5 = 18.
(1, 8): The sum of whol+e array is 9 + 2 + 2 + 5 + 11 + 0 + 2 + 4 = 35.

Also read, Euclid GCD Algorithm

Approach

Brute force approach

The most straightforward approach is to run a loop from i = 1 to i = l and calculate the sum of elements, and for updates, change the value at the index ind. The time complexity of query operation is O(N), and for the update, it is O(1). This solution will work if the update operations are more frequent compared to query operations. Otherwise, it will give the verdict "Time Limit Exceeded".

Another approach is to calculate the prefix sum first, then answer the query in O(1) and perform the update in O(N). It will still give TLE if the query and update operation is comparable.

Efficient Approach

We can solve this problem efficiently by using the segment tree. Using the segment tree, we can perform both operations in O(log N) complexity.

We can also use the binary index tree (BIT)/Fenwick tree. It performs both operations in O(log N) complexity like the segment tree. The advantage of using BIT over the segment tree is that it requires less space and is very easy to implement.

Basic Idea of BIT

The idea is to maintain an array Tree[] in which each index represents a node and stores the sum of some elements of the given array. 

The size of Tree[] is the same as the input array. To avoid runtime error, we will use a size of N + 2.

Let's take an example to understand the construction of BIT.

Let the given array be, 

int a[] = {0, 9, 2, 1, 5, 11, 0, 2, 4}

For simplicity, let's assume that the array provided is 1-based indexed.

We will use the least significant 4 bits as there are only eight elements.
 

The above figure shows the binary index tree for an array of size 8.

As shown in the figure - 

Node 0 (0000) is the dummy node. It has 4 unset bits, so it has four children: node 1 (0001), 2 (0010), 4 (0100), and 8 (1000).

Similarly, in node 4 (0100), there are two unset bits after the last set bit, so it has two children: node 5 (0101) and 6(0110).

Node 7 (0111) does not have any unset bit after the last set bit, so it has no children.

In general, for node u, if we remove the last set bit, we will get its parent.

parent of node u = u - u &(-u)

The above figure also shows the range of each node. For example, node 4 stores the sum of range [1, 4], node 8 stores the sum of the whole array, and node 5 stores the sum of range [5, 5]. 

To generalize this, each node u stores the sum of the range [u - (1 << r) + 1, i ], where r is the last set bit in the binary representation of u.

How to answer the queries efficiently??

As we know, each node u stores the sum of range [u - (1 << r) + 1, i ] therefore, to compute the answer for query(u), we will start from node u and add its value (Tree[u]) to the result, then we will move to its parent (u - (u - (1 << r))) and perform the same operation until we reach node zero (dummy node). The final result obtained will give us the sum of the range [1, u].

At every step, we remove the last set bit to reach the current node's parent, and there can be at max log(u) set bits in the binary representation of u, so in the worst case, the time complexity is O(log N).

How to perform update operation??

If we want to update the element at the index ind with value val, we have to add val - a[ind] at every node u which contains index ind in its range.

We can achieve this using the formula u + u&(-u). We will start from u = ind and add val - a[ind] to Tree[u], then we will move to the next node (u + u&(-u)) and perform the same operation until u becomes greater than N. 

The formula basically adds decimal value corresponding to the last set bit from u. For example, if u = 6 (0110), the last set bit is 2^1, so we will add 2 to get the next node (u = 8).

As there can be at max log N set bits in binary representation of u, the worst-case time complexity is O(logN).
 

Code

#include <bits/stdc++.h>
using namespace std;
const int maxN  = 3e5 + 7;
//array to store BIT
int Tree[maxN];
//size of input array
int N;
//function to answer the query
int query(int ind){
   int result = 0; 
   //traversing the ancestors of node ind
   while(ind > 0){
       result += Tree[ind]; // add value at current node to result.
       ind -= (ind & -ind); // remove the last set bit to get the parent
   }
   return result;
}
//function for update
void update(int ind, int change){
   while(ind <= N){    
       //add the change to the node
       Tree[ind] += change; 
       //use to formula u + u&(-u) to get the next element
       ind += (ind & -ind);
   }
}
int main(){
   //size of input array
   cin >> N;
   //input array
   int a[N + 2];
   for(int i = 1; i <= N; ++i){
       cin >> a[i];
   }
   //update a[i] for every i 
   for(int i = 1; i <= N; ++i){
       update(i, a[i]);
   }
   //number of queries
   int Q;
   cin >> Q;
   while(Q--){
       /*
           type of query
           1 - query
           0 - update
       */
       bool type;
       cin >> type;
       if(type){
           //calulate the sum of prefix of length l
           int l;
           cin >> l;
           //function call
           cout << query(l) << "\n";
       }
       else{
           //update element at ind with element val
           int ind, val;
           cin >> ind >> val;
           /*
               a[i] + change = val
               change = val - a[i]; 
           */
           int change = val - a[ind];
           //function call
           update(ind, change);
           a[ind] = val;
       }
   }
   return 0;
}

Input

8
9 2 1 5 11 0 2 4
4
1 4
0 3 2
1 4
1 8

Output

17
18
35

Time Complexity

As there are Q queries, the total time complexity is O(Q log N).

Space Complexity

The space complexity is O(N).

Check out this problem - Count Inversions

FAQs

1. Can we use the binary index tree to answer the range sum query?
   Yes, the answer for the range [l, r] is query(r) - query(l - 1).
    
2. Can we use the binary index tree to answer the range GCD query?
   We can't use BIT for range GCD or range min/max query. It can be used only for invertible functions like sum, product, etc.
    
3. What are the applications of the binary index tree?
   It can be used to count the inversions of the given array in O(N log N) time complexity.

Key Takeaways

In this article, we discuss BIT and see its implementation in c++. BIT is an efficient data structure to answer the range query for invertible functions. Check out this problem to get a better hold on it.

To learn more about such data structures and algorithms, Coding Ninjas Studio is a one-stop destination. This platform will help you to improve your coding techniques and give you an overview of interview experiences in various product-based companies by providing Online Mock Test Series and many more benefits.

Happy learning!