1.
Introduction
2.
Problem Statement
3.
Solution Approach
3.1.
C++ implementation
3.2.
Complexities
4.
5.
Key Takeaways
Last Updated: Mar 27, 2024

# Binary Indexed Tree: Range Update and Range Queries

Shreya Deep
0 upvote

## Introduction

This article we will learn how to answer range update and range sum queries using a Binary Indexed Tree (also known as Fenwick tree).

Binary Indexed tree or a Fenwick tree is an advanced data structure used to solve range-based queries. It supports query (prefix sum calculations) and updates in logarithmic time complexity. Range queries ask us to do an operation or return the asked parameter on a range of indexes in an array.

## Problem Statement

Given an array a, of n integers, initially containing all zeros, you are required to perform some operations on it. The operations or the queries, are of two types:

• update (l,r,val): update the numbers from index i =l to i = r to a[i] = a[i] + val
• getRangeSum(l,r): Calculate and return the sum of numbers from index i = l to i = r.

For example

Input

``````n = 6, q = 3
Query 1: update(2,5,3)
Query 2: update(0,3,4)
Query 3: getRangeSum(1,4)``````

Output

``21``

Explanation: Initially, the array will be [0,0,0,0,0,0]. After query 1, the array will be [0,0,3,3,3,3]. After query 2, the array will be [4,4,7,7,3,3]. For query 3, we need the sum from index 1 to index 4. So the sum is 4+7+7+3 = 21.

Note: The indexing of the array starts from 0 here.

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

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

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 treerearrange the positions by heightninja, and timecount of smaller elementsreverse 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!

Live masterclass