Range Sum Queries and Update with Square Root

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.

If you aren’t familiar with Binary Indexed Tree data structure, you can visit this fantastic article on Coding Ninjas to learn more about this topic.

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