SQRT Decomposition

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.

Space Complexity

O(N), as we are creating an array of size ‘N’.

Check out this problem - Longest Subarray With Sum K 

Frequently Asked Questions

What is the 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.

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:

• Rabin Karp Algorithm
• Group Words with Same Set of Characters
• Count Divisible Pairs in an Array
   

Please refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. And also, enroll in our courses and refer to the mock test and problems available. Have a look at the interview experiences and interview bundle for placement preparations.

Keep learning, Keep Growing!