## 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:** 5

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