1.
Introduction
2.
Problem Statement
3.
Brute Force Approach
4.
Approach: Efficient
5.
Implementation
6.
Complexity
7.
FAQs
8.
Key Takeaways
Last Updated: Mar 27, 2024

# Range Sum Queries and Update with Square Root

## Introduction

The problem, Range Sum Queries, is based on the topic Binary Indexed Tree, which is quite an asked problem in the technical rounds of the product-based companies.

A Binary Indexed tree or Fenwick tree is a data structure that can efficiently update elements and calculate prefix sums in a table of numbers.

## Problem Statement

We will be given an array ‘arr’ of ‘n’ elements and ‘q’ number of queries. And there are two types of queries:

Update [L, R]: Updating the array elements from L to R with their square roots.

Query [L, R]: Computing the sum of array elements from L to R.

Let’s understand the problem statement with the help of some examples for more clarity.

Example1:

Input: arr[] = { 4, 9, 25, 36 }, q = {{1, 2, 4}, {2, 1, 4}}

Output: 18

Note:

Considering the 1-based indexing.

Explanation:

For the first query, the first element is ‘1’, which means we will update the elements with square root according to the range mentioned in the query. The second and third elements of the first query are ‘2’ and ‘4’, respectively, which are the index of the ranges we have to update the array elements.

After updating array will be: {4, 3, 5, 6}- square root of 9,25,36 is 3,5,6 respectively.

For the second query, the first element is ‘2’, which means we will calculate the range sum from the range mentioned in the query. The second and third elements of the first query are ‘1’ and ‘4’, respectively, which are the index of the ranges we have to calculate the sum of the array elements.

The sum of elements will be 4+3+5+6=18.

Example2:

Input: arr[ ] = { 9, 4, 1, 5, 2, 3 }, q[ ] = { {1, 1, 3}, {2, 1, 2}, {1, 2, 5}, { 1, 4, 5}}

Output:

Explanation:

For the first query, the first element is ‘1’, which means we will update the elements with square root according to the range mentioned in the query. The second and third elements of the first query are ‘1’ and ‘3’, respectively, which are the index of the ranges we have to update the array elements.

After updating array will be: {3, 2, 1, 5, 2, 3}- square root of 9,4,1 is 3,2,1 respectively.

For the second query, the first element is ‘2’, which means we will calculate the range sum from the range mentioned in the query. The second and third elements of the first query are ‘1’ and ‘2’, respectively, which are the index of the ranges we have to calculate the sum of the array elements.

The sum of elements will be 3+2=5.

For the third query, the first element is ‘1’, which means we will update the elements with square root according to the range mentioned in the query. The second and third elements of the first query are ‘2’ and ‘5’, respectively, which are the index of the ranges we have to update the array elements.

After updating, the array will be: {3, 1, 1, 2, 1, 1}

For the fourth query, the first element is ‘1’, which means we will update the elements with square root according to the range mentioned in the query. The second and third elements of the first query are ‘4’ and ‘5’, respectively, which are the index of the ranges we have to update the array elements.

After updating, the array will be: {3, 1, 1, 2, 1, 1}

Let’s look for a naive approach first.

## Brute Force Approach

We can iterate the queries array till the end perform the two operations(update and query), but the time complexity will be O(q*n).

## Approach: Efficient

• To decrease the number of iterations, we will be using Binary Indexed Tree or Segment Trees.
• Construct an array total[] storing max as 100.
• Construct two functions update[l,r] and sum[l,r] to perform the two operations.
• Declare a Set of integer types to store the index of only those numbers greater than ‘1’.
• To find the l index of the update query use binary search and increment the l index until every element is updated in the range of that update query.
• If the updated value becomes 1, remove it from the set as it will always be 1 even after any next update query.
• For range sum query operation, do query(r) – query(l – 1).

## Implementation

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

// Maximum size of input array
const int MAX = 100;

int total[MAX + 1];

// structure for queries with members type,
// leftIndex, rightIndex of the query
struct queries {
int type, l, r;
};

// For updating the query
void update(int x, int value, int n)
{
for (x; x <= n; x += x & -x) {
total[x] += value;
}
}

// To find the sum
int sum(int x)
{
int temp = 0;
for (x; x > 0; x -= x & -x) {
temp += total[x];
}
return temp;
}

// function to return answer to queries
void queries_total(int arr[], queries que[], int n, int q)
{
// Declaring a Set of integer type
set<int> s;
for (int i = 1; i < n; i++) {

// store the index value of only those numbers
//which are greater than 1
if (arr[i] > 1)
s.insert(i);
update(i, arr[i], n);
}

for (int i = 0; i < q; i++) {

// update query
if (que[i].type == 1) {
while (true) {

auto j = s.lower_bound(que[i].l);

if (j == s.end() || *j > que[i].r)
break;

que[i].l = *j;

// By using the update query update the
//value of arr[i] to its square root
update(*j, (int)sqrt(arr[*j]) - arr[*j], n);

arr[*j] = (int)sqrt(arr[*j]);

// if updated value = 1,
// remove it from the set s
// The reason is that it will always be 1
//even after any next update query.
if (arr[*j] == 1)
s.erase(*j);

// increment the index
que[i].l++;
}
}

// For sum query operation
else {
cout << (sum(que[i].r) - sum(que[i].l - 1)) << endl;
}
}
}

// Main function
int main()
{
int q = 4;

// intializing '0' starting to consider the 1-based indexing.
int arr[] = { 0,9, 4, 1, 5, 2, 3 };
int n = sizeof(arr) / sizeof(arr[0]);

// array for queries
queries que[q + 1];

que[0].type = 1, que[0].l = 1, que[0].r = 3;
que[1].type = 2, que[1].l = 1, que[1].r = 2;
que[2].type = 1, que[2].l = 2, que[2].r = 5;
que[3].type = 1, que[3].l = 4, que[3].r = 5;

queries_total(arr, que, n, q);

return 0;
}``````

Output

``5``

## Complexity

The time complexity to solve this efficient approach is O(logn) for each query. Therefore the overall time complexity is Q*(log n).

The space complexity is O(n) for declaring an array.

Check out this problem - Two Sum Problem

## FAQs

1. What do you mean by Binary Indexed Trees?
Binary Indexed Tree or Fenwick Trees represents array elements, allowing prefix sums to be calculated efficiently. The Fenwick tree achieves a much better balance between two operations: element update and prefix sum calculation.

2. What is the time complexity to solve the efficient approach?
The time complexity to solve an efficient approach using Binary Indexed Trees is O(logn) per query.

## Key Takeaways

This blog has covered the following things:

• What exactly the problem statement is, along with some detailed examples.
• Efficient approach and the implementation in CPP language.

Also, you can practice more Range Query problems to raise your bar in competitive programming.

Don’t forget to practice the wide variety of DSA problems frequently asked in interview rounds readily available on Coding Ninjas Studio

Happy Coding!!!

Live masterclass