Binary Indexed Tree: Range Update and Range Queries

Solution Approach

The most straightforward method to solve this problem is to make an array of size n and do the required query operations on the array one by one. For update query, traverse the array from index l to r, and update the values. Similarly, for range sum queries, we traverse the array from index l to r and find the required sum. But if you notice, here, the time complexity will be O(n) for each query in the worst case. So, if there are n queries in total, the total time complexity will be O(n^2), which is inefficient. So, let's look at the efficient approach!

We can use a data structure called a Binary Indexed tree to solve this problem and answer the queries faster. What we will do here is we will create a Binary Indexed tree of size n+1 which will store the elements. 

• For the update query: we can add the value "val", to the index l and subtract "val" at index r+1. Why do we do this? Because the update query asks us to add "val" to each number from index l. So, by adding "val" at index l, we mean that we are adding "val" to each index from l to end. Now, since we wanted to add "val" till index r only, for all the indexes from r+1 to n, we need to subtract "val." We can add "-val" to index r+1. 
   
• For the range sum query: If we are given the indexes l and r, it's clear that the range sum will be prefix sum till index r - prefix sum till index l-1. It's easy to precalculate the prefix sum if the values at the indices are not changing. But in this case, some of the values change with each update query. So how do we take care of that? Let's see an example. Suppose we need to calculate the range sum [0,b]. Before this query, let's say there was an update query on index[l,r]. How does this update query affect the sum of range [0,b]? 
  There can be three different cases:
  • If b<l: In this case, the values from the index [0,b] are not affected by the update query, and therefore the range sum doesn't get involved.
     
  • If l<b<r: In this case, the range sum gets incremented by (val*(b) - val(l-1)), where "val" is the value by which numbers from index l to r were updated in the update query. 
     
  • If b>=r: In this case, the range sum gets incremented by (val*(r) - val(l-1)), where "val" is the value to which numbers from index l to r were updated in the update query.

Let's use another Binary Indexed tree for storing the value of val*(l-1) for each such l. Then, whenever an update query is called, we also update the values of val*(l-1) for each l. Suppose an update query is called on the range [l,r] with "val." First, in the first BIT, we add "val" to index l and subtract "val" from index r. Then, in the second BIT, we add "val*(l-1)" at index l and subtract "val*r" at index r+1.

Also, since we have to add "val*(l-1)", we will take the BIT of size n+1 rather than just n and start from index one so that l-1 is never negative.

Now, we can easily say, for answering the range sum query, the range sum of range[0,b] = getSum((value at index b in BIT1)*b) - getSum((value at index b in BIT2). 

Note: getSum is the conventional function for getting a BIT prefix's sum. If you don't know about this, kindly read here first.

Steps of implementation are:

• Declare and initialize the two BITs
   
• Take the input queries. 
   
• For each update query:
  • Call the function "update", which performs the update operation. In this function, call the function updateBIT for index l,r+1 with val and -val respectively, for the first BIT, and for index l, r+1 with val*(l-1) and -val*(r) respectively for the second BIT. The "updateBIT" function updates the value at a particular index and its ancestors. In the function updateBIT:
    • Increment the index by the BIT in one-indexed because its size is n+1.
       
    • Traverse all the ancestors of the index, and add val to their value.
       
• For each range sum query:
  • Call the function "rangeSum," which performs the range sum query and returns the required sum. In this function, call the function "sum," which returns the prefix sum till r and l-1, subtract them, and return the answer. In the function sum, return sum as getSum((value at index b in BIT1)*b) - getSum((value at index b in BIT2). Here, getSum is the function that returns the sum of a prefix, given the last index of the prefix. In the function “getSum()”:
    • Declare a variable "sum," which will store the answer and initialize it to zero.
       
    • Increment the index by one as the BIT is one-indexed because its size is n+1.
       
    • Traverse all the ancestors of the index, and add their value to the variable sum.
       
    • Return the calculated sum.
       
  • Print the value returned by the function rangeSum.

C++ implementation

#include <bits/stdc++.h>
using namespace std;

/*
    Class of Binary Indexed Tree
*/
class BIT{
    public:
        /*
            Vector for storing the elements of BIT
        */
        vector<int>bit;
        /*
            Initialise the vector with size = n+1 and all values equal to 0
        */
        BIT(int n){
            bit.assign(n+1, 0); 
        }
};

/*
    Function that returns the sum of a prefix, given the last index of the prefix
*/
int getSum(vector<int>&bit1, int index){
    /*
        Declare a variable "sum", which will store the answer, and initialise it to zero.
    */
    int sum = 0; 
    /*
        Increment the index by as the BIT is one-indexed because its size is n+1.
    */
    index = index + 1;
    /*
        Traverse all the ancestors of the index, and add their value to the variable sum.
    */
    while (index>0)
    {
        sum += bit1[index];
        index -= index & (-index);
    }
    return sum;
}

/* 
    Function to update the value at a particular index and its ancestors
*/
void updateBIT(vector<int>&bit1, int n, int index, int val){
    /*
        Increment the index by as the BIT is one-indexed because its size is n+1.
    */
    index = index + 1;
    /*
        Traverse all the ancestors of the index, and add val to their value.
    */
    while (index <= n)
    {
        bit1[index] += val;
        index += index & (-index);
    }
}

/*
    Function that returns the prefix sum of updated bit1 and bit2
*/
int sum(int x, vector<int>&bit1, vector<int>&bit2){
    /*
        Return sum as getSum((value at index b in BIT1)*b) - getSum((value at index b in BIT2)
    */
    return (getSum(bit1, x) * x) - getSum(bit2, x);
}

/*
    Function that performs the update operation
*/
void update(vector<int>&bit1, vector<int>&bit2, int n, int val, int l, int r){

    /*
        Update bit1 at index l and r+1
    */
    updateBIT(bit1,n,l,val);
    updateBIT(bit1,n,r+1,-val);

    /*
        Update bit2 at index l and r+1
    */
    updateBIT(bit2,n,l,val*(l-1));
    updateBIT(bit2,n,r+1,-val*r);
}

/*
    Function that performs the range sum operation and returns the required sum
*/
int rangeSum(int l, int r, vector<int>&bit1, vector<int>&bit2)
{
    /*
        Call the function sum, which returns the prefix sum till r and l-1, subtract them, and return the answer.
    */
    return sum(r, bit1, bit2) - sum(l-1, bit1, bit2);
}


int main()
{
    int n = 6;
    /*
        Declare and initialise the two BITs
    */
    BIT BIT1 = BIT(n);
    BIT BIT2 = BIT(n);
    /*
        update query: add 3 to all the elements from [2,5]
    */
    int l = 2 , r = 5 , val = 3;
    update(BIT1.bit,BIT2.bit,n,val,l,r);

    /*
        update query: add 4 to all the elements from [0,3]
    */
    l = 0 , r = 3 , val = 4;
    update(BIT1.bit,BIT2.bit,n,val,l,r);

    /*
        Range sum query: Find the sum of elements from index 1 to 4.
    */
    l = 1 , r = 4;
    cout << "Sum of elements from index " << l << " to " << r << " is "<<rangeSum(l,r,BIT1.bit,BIT2.bit) << "\n";

    return 0;
}

Output

Sum of elements from index 1 to 4 is 21

Complexities

• Time complexity

O(q*logn), where q is the number of queries and n is the number of elements in the vector.

Reason: For each query, whether the update or the range sum, the time complexity is logn because the only time taken is traversing through an index's ancestors. And since the height of a tree will be at most logn, there will be at most logn ancestors. Thus, for q queries, the total time complexity will be O(q*logn).

• Space complexity

O(n), where n is the number of elements in the vector.

Reason: The only space taken is by the vectors bit1 and bit2. Thus, the space complexity is O(2*n) = O(n).

Check out this problem - Two Sum Problem

Frequently asked questions

1. What is Fenwick Tree or Binary Indexed Tree?
   A Fenwick tree or Binary Indexed Tree is a data structure that allows efficient calculations of prefix sums and efficient updates of elements in the array (while retaining tree structure & all its properties). 
    
2. What is the time complexity of insertion and query in a Fenwick Tree or Binary Indexed Tree?
   The time complexity of insertion and deletion in a Binary Indexed Tree containing N elements is O(logN).
    
3. What is the advantage of Fenwick tree over Segment tree?
   The main advantage of the Fenwick tree is that it requires less space, is relatively simple to implement, and has concise code.
    
4. What is the disadvantage of the Fenwick tree over the Segment tree?
   We can only use the Fenwick tree in queries where L=1. Therefore it cannot solve many problems.

Key Takeaways

This article discussed implementing update and range sum queries on a binary indexed tree. It is recommended that you try problems based on this topic. Some of them are: Fenwick tree, rearrange the positions by height, ninja, and time, count of smaller elements, reverse pairs and count even or odd.

Are you planning to ace the interviews of reputed product-based companies like Amazon, Google, Microsoft, and more? 

Attempt our Online Mock Test Series on Coding Ninjas Studio now!

Happy Coding!