Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
1.
Introduction-
2.
Solution Approach
2.1.
Algorithm -
2.2.
C++ code:
2.3.
Algorithm Complexity:
3.
FAQs
4.
Key takeaways-
Last Updated: Mar 27, 2024

# Range Update and Range Queries in Binary Indexed Tree

Riya
1 upvote

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

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

## FAQs

1. What is a Binary Indexed Tree?
A Binary indexed tree, also known as the 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 a sum of powers of 2.

2. What is the time complexity of range update and range queries in Binary Indexed Tree?
The time complexity of both range update and range queries in binary indexed tree is O(logN), where N is the size of the binary indexed tree.

## Key takeaways-

This article discussed “Range update and Range Queries in Binary Indexed Tree," its C++ implementation, and its time and space complexity. If you want to solve more problems on data structure and algorithms for practice, you can visit Coding Ninjas Studio.

If you think that this blog helped you, then share it with your friends!. Refer to the DSA C++ course for more information.

Check out this problem - Diameter Of Binary Tree

Until then, All the best for your future endeavours, and Keep Coding.

Live masterclass