In this blog, we will discuss the topic of square root decomposition(SQRT Decomposition). SQRT Decomposition based-coding problems are widely asked in coding contests and various coding interviews.

Sqrt decomposition (or Square Root decomposition) is a technique used in programming to optimize evaluating some common queries on an array. Let us have a detailed discussion on it with the help of an example.

Given an array of integers ‘ARR’ of size ‘N’ and the number of queries ‘Q’ wherein each query, you are given two integers ‘L’ and ‘R’ (L < = R < N). For each query, For each query, the task is to evaluate the sum of the elements in the subarray from index L to R of the given array.

For example,

Suppose, ARR = {3, 2, 1, 4, 4, 5, 3, 2, 1}. Q = 2, the queries are given as:
L = 1 and R = 5, so here we need to calculate our result in {2, 1, 4, 4, 5}. The result is 16.
L = 4 and R = 8, so here we need to calculate our result in { 4, 5, 3, 2, 1}. The result is 15.
Here, the indexing starts from 0.

Solution Approaches

The following approaches can be taken to solve this problem:

Bruteforce Approach

The naive approach to solving the above problem is to traverse all the elements of the subarray.

After that, find the minimum out of them.

The time complexity in this approach is O(Q * N).

We can solve the above problem in O(sqrt(N) * Q) by using SQRT decomposition.

Let’s discuss the SQRT decomposition approach.

SQRT Decomposition Method

It is the method used to find the result of operations gcd, min, max, etc of the subarray in O(sqrt(N)) time.

In this method, an array ‘BLOCK’ of size sqrt(N) is created where each ‘BLOCK[i]’ (i <= sqrt(N)) is used to store the minimum element in the subarray starting from i*sqrt(N)^{th} index and ending on (i+1)*sqrt(N)^{th} index.

This is done so that when any query is made, then we don’t need to check the whole subarray, we only need to check the value of that block and upgrade our result accordingly.

If some parts of the subarray partially lie on any block, in that case, iterate that block to get the result of that block.

In the worst case, the time complexity of building the block is O(N), and getting the minimum element in any subarray is O(K*3), where ‘K’ is the square root of ‘N’.

Dry Run

Step 1: First, declare three global variables: 'a[]' and 'blocks[]' to store the specified array and the precomputed sum of each block, respectively, and an integer 'blockSize' to hold the size of each block.

Step 2: We will write a function called 'preCompute()' that divides the given array into small blocks of size sqrt(n) and then precomputes the results. We will then find the size of each block within the function, store it in the globally declared variable 'blockSize,' and then traverse the specified array, storing the sum of each block of size'sqrt(n)' in the array 'blocks[]'.

Step 3: We will create the method 'evaluateQueries()' to evaluate queries for calculating the sum of a given subarray using sqrt decomposition. We will then declare a vector to store the answer to each query within the function, then execute a loop and invoke the function 'findSum()' to find the sum of the subarray of each query.

Step 4: Then, using sqrt decomposition, we will write the method 'findSum()' to find the sum of the subarray a[left, right]. We will then calculate the sum of the first block in the query's range, then the sum of the blocks totally inside the query's range, and finally the sum of the last block within the query's range. Finally, return the grand total.

Step 5: Finally, within the main function, we will print the answer to each question that was returned by the function 'evaluateQueries()'.

C++ Implementation

// C++ program to evaluate the queries of finding sum of elements in a given subarray using sqrt decomposition.
#include <bits/stdc++.h>
using namespace std;
// To store given array, assuming the maximum size of the array can be 10^6
int a[1000000];
// To store the precomputed sum of each block
int blocks[1000];
// Size of each block
int blockSize;
// Function to divide the given array in the small blocks of size sqrt(n) and precompute the results
void preCompute(int arr[], int n)
{
// Size of each block
blockSize = sqrt(n);
// Initializing index of blocks
int blockIndex = -1;
for (int i = 0; i < n; i++)
{
a[i] = arr[i];
if (i % blockSize == 0)
{
// Move to the next block
blockIndex++;
}
// Storing the sum of elements of a block of size sqrt(n)
blocks[blockIndex] += a[i];
}
}
// Function to find sum of the subarray a[left, right] using sqrt decomposition
int findSum(int left, int right)
{
// First, calculating the sum of the first block in the range of the query
int sum1 = 0;
while (left != 0 && left < right && left % blockSize != 0)
{
sum1 += a[left];
left++;
}
// Calculating the sum of the blocks completely inside the range of the query
int sum2 = 0;
while (left + blockSize <= right)
{
// Find the index of the current block
int index = left / blockSize;
sum2 += blocks[index];
left += blockSize;
}
// Calculating the sum of the last block in the range of the query
int sum3 = 0;
while (left <= right)
{
// traversing last block in range
sum3 += a[left];
left++;
}
// Return the total sum
return sum1 + sum2 + sum3;
}
// Function to evaluate queries of finding sum of a given subarray using sqrt decomposition
vector < int > evaluateQueries(int queries[][2], int q)
{
// Vector to store the sum of subarray for each query using sqrt decomposition
vector < int > res;
// Evaluating each query
for (int i = 0; i < q; i++)
{
int sum = findSum(queries[i][0], queries[i][1]);
res.push_back(sum);
}
return res;
}
// Main Function
int main()
{
int n;
cout << "Enter array size" << endl;
cin >> n;
int arr[n];
cout << "Enter array elements" << endl;
for (int i = 0; i < n; i++)
{
cin >> arr[i];
}
// Given number of queries
int q;
cout << "Enter number of queries" << endl;
cin >> q;
/*
Query 1: {3, 8}
Query 2: {1, 6}
Query 3: {8, 8}
*/
int queries[q][2];
cout << "Enter queries" << endl;
for (int i = 0; i < q; i++)
{
for (int j = 0; j < 2; j++)
{
cin >> queries[i][j];
}
}
// Call the function to divide the given array in the small blocks of size sqrt(n) and precompute the results
preCompute(arr, n);
// Call the function to evaluate the queries using sqrt decomposition technique
vector < int > ans = evaluateQueries(queries, q);
cout << "Output Generated" << endl;
// Printing the answers for each Query
for (int i = 0; i < q; i++)
{
cout << "Query " << i + 1 << ": " << ans[i] << endl;
}
return 0;
}

Input:

Enter array size

9

Enter array elements

3 2 1 4 4 5 3 2 1

Enter number of queries

3

Enter queries

3 8

2 6

8 8

Output:

Explanation:

Here we have taken 3 queries.

The first query is {3,8} which gives an output of “19” as the elements get added from index 3 to 8.

sum=4+4+5+3+2+1=19

The second query is {2,6} which gives an output of “17” as the elements get added from index 2 to 6.

sum=1+4+4+5+3=17

The third query is {8,8} which gives an output of “1” as the elements get added from index 8 to 8.

sum=1

Complexities

Time Complexity

O(Q * sqrt(N))

For each query, the "update()" and "query()" functions with time complexity of log(N) are called in the function "evaluateQueries()" to evaluate the queries to determine the sum of elements less than or equal to a specified number in a particular subarray. As a result, the overall time complexity is O(Q * log(N)), where 'Q' and 'N' are the number of searches and array entries, respectively.

It is the method used to find the result of operations gcd, min, max, etc., of the subarray in O(sqrt(N)) time.

What is the vector in C++?

Vector is a dynamically sized array in the C++ STL library. It is very useful as it provides various built-in functions to add, insert, remove, pop elements, etc.

How can we add an element at the end of a vector?

To add an element at the end of a vector, we can use vector_name.push_back() function. This function takes the element to be added as an argument.

How is the performance of an algorithm measured?

To measure the performance of an algorithm and compare two algorithms, we use the time and space complexities of the algorithm.

What is meant by the brute force approach?

Brute force is the most basic approach to solving a problem which takes the most time.

Conclusion

In this blog, we have learned the concept of SQRT Decomposition, and we have seen how we can reduce the time complexity using this method, and then we have discussed one problem based on this topic and analysed the input and output.

If you found this one interesting, explore our other Data Structures and Algorithm related blogs as well: