Range Update and Range Queries in Binary Indexed Tree

Introduction-  

This blog will discuss how to solve problems of Range update and Range Queries in Binary Indexed Tree. Before moving further, let's recall what a Binary Indexed Tree is.

"Binary indexed tree also known as Fenwick tree is a data structure that stores the elements in an array and helps to calculate the prefix sum efficiently. This data structure is based on the fact that every positive integer can be represented as the sum of powers of 2."

Now, let's take an example problem of Range Update and Range Queries:

Suppose we have an array containing 'N' integers, and we have to perform the following two operations:

1. Update {x, L, R}: In this operation, we have to update the array elements having indices in the range of [L, R]. Add 'x' to each array element having indices in this range of [L, R]. This is an example of Range Update.
2. Query{L, R}: In this operation, we have to find the sum of array elements having indices in the range of [L, R]. This is an example of Range Query.

We have to perform the above two operations for a given array using a Binary Indexed Tree. We will be given an integer 'n', which means we have to take an array of size 'n' and all its elements will be initially equal to zero, and 'Q' number of queries which will be either a Range Update Query or Range Sum Query and we will have to solve the queries using a Binary Indexed Tree.

To know more about Introduction to JQuery check this out.

Solution Approach

This section will discuss the approach to evaluate update and range queries in binary indexed tree. The Range Sum query can be evaluated using prefix sums. Let's say we have to find the sum in the range [L, R]; we can find this by subtracting the prefix sum [0, L-1] from the prefix sum [0, R]. We know that 'Prefix sum' can be calculated in binary indexed trees in O(log N) time. But here, we also have range update queries, so we have to update the binary indexed tree for given range update queries in such a way that the range sum query can be calculated correctly in log(N) time. 

Suppose we have a range update query for [L, R], and after this, we need to find prefix sum [0, M]. Then following three cases can arise:

Case 1. M < L

In this case, the sum of the range [0, M] won't be affected by an update in the range [L, R]

Case 2: L < M < R

In this case, the sum of the range [0, M] will be increased by "(x*M - x*(L-1))" after updating the range [L, R] (Here updating range [L, R] means adding 'x' to each element in the range [L, R]).

Case 3: M > R

In this case, the sum of the range [0, M] will be increased by "(x*R - x*(L-1))" after updating the range [L, R], as we need to add ‘x’ to each element of the range [L, R]  

We can see here that for cases 2 and 3, we need to add some extra terms in prefix sum to get the answer of the range sum query after a range update query. We will maintain two binary indexed trees - one for getting the element at a given index and another for getting the value of (x*(L-1)) after each range update query. Using these two binary indexed trees, we can perform the range update query and evaluate the sum range query in logarithmic time complexity.

Algorithm -

Step 1. First the main function. Inside the main function, first, create the variables to store the given array and the number of elements in the array and then create two binary indexed trees as discussed in the previous section. Initialize each element of the binary indexed trees with zero.

Step 2. Next, for each query, call the functions "rangeUpdateQuery()" and "rangeSumQuery()" depending on the type of query, whether it is a range update query or a range sum query.

Step 3. Create a function "rangeSumQuery()," which takes the two binary indexed trees, L and R, as inputs and returns the sum of the elements of the range [L, R]. Inside the function, it finds the prefix sum [0, R] and [0, L-1] and subtract the prefix sum [0, L-1] from the prefix sum [0, R] to get the required sum of the range [L, R].

Step 4. Create a function "rangeUpdateQuery()" which calls the function "update()" to update both the binary indexed tree such that one binary indexed tree can be used to get the value at any index, and the other can be used to get the value of (x*(L-1)) after each update query.
 

C++ code:

// C++ program to demonstrate Range Update and Range Queries in Binary Indexed Tree
#include <bits/stdc++.h>
using namespace std;

// Updates a node in Binary Index Tree (BITree) at a given index in BITree. Add 'x' to BIT[i] and all of its ancestors
void update(int BIT[], int n, int index, int val)
{

	// index in BITree[] is 1 more than the index in arr[]
	int i = index + 1;


	// Traverse all ancestors and add 'val'
	while (i <= n)
	{
		BIT[i] += val;
		i += i & (-i);
	}
}

void rangeUpdateQuery(int BIT1[], int BIT2[], int n, int val, int l, int r)
{

	// Update BIT1
	update(BIT1,n,l,val);
	update(BIT1,n,r+1,-val);


	// Update BIT2
	update(BIT2,n,l,val*(l-1));
	update(BIT2,n,r+1,-val*r);
}

int getSum(int BIT[], int index)
{
	int sum = 0; 


	// index in BITree[] is 1 more than the index in arr[]
	int i = index + 1;


	// Traverse ancestors of BITree[index]
	while (i > 0)
	{
		sum += BIT[i];
		i -= i & (-i);
	}
	return sum;
}

int rangeSumQuery(int BIT1[], int BIT2[], int l, int r)
{

	// Sum of elements in [0, r]
	int sum1 = (getSum(BIT1, r)*r) - getSum(BIT2, r);

	// Sum of elements in [0, l-1]
	int sum2 = (getSum(BIT1, l-1)*(l-1)) - getSum(BIT2, l-1);

	// Sum of elements in [l,r] = Sum of elements in [0,r] - Sum of elements in [0, l-1]
	return sum1-sum2;

}

// Main Function
int main()
{

	// Number of elements in the given array
	int n = 6;

	// Given array
	int arr[6] = {0, 0, 0, 0, 0, 0};
    	
	// Construct a binary indexed tree to get an element at a given index in the array
	int *BIT1 = new int[n+1];

      	//Initialize each element with zero
	for(int i=1; i<=n; i++)
	{
		BIT1[i] = 0;
	}

	// BIT 2 maintains the extra term which needs to be subtracted
	int *BIT2 = new int[n+1];

	//Initialize each element with zero
	for(int i=1; i<=n; i++)
	{
		BIT2[i] = 0;
	}
 
	// First Query: Range Update Query : Add 5 to all the elements from [0,4]
	int l = 0 , r = 3 , val = 4;
	rangeUpdateQuery(BIT1,BIT2,n,val,l,r);


	// Second Query: Range Update Query : Add 2 to all the elements from [2,4]
	l = 1 , r = 4 , val = 6;
	rangeUpdateQuery(BIT1,BIT2,n,val,l,r);


	// Third Query: Range Query : Find sum of all the elements in the array from [1, 4]
	l = 0 , r = 5;
	int sum = rangeSumQuery(BIT1, BIT2, l, r);
	cout << "Sum of elements from [" << l << "," << r << "] is ";
	cout << sum << "\n";

	return 0;
}

Output:
Sum of elements from [0,5] is 40

Algorithm Complexity: 

Time Complexity: O(Q * log(N))

In the above program to demonstrate range update and range queries in binary indexed tree, both range update, and range query takes O(logN) time. So, the overall time complexity is O(Q* log(N)), where 'Q' and 'N' are the number of queries and number of elements in the array, respectively.

Space Complexity: O(N) 

In the above program to demonstrate range update and range queries in binary indexed tree, we have created two arrays of size (N+1) for two required binary indexed trees. So, overall space complexity is O(N), where 'N' is the number of elements in the given array.

Also read, Euclid GCD Algorithm