In this blog, we will first learn about the ‘sqrt decomposition’ technique then we will solve a problem using this technique.
Sqrt decomposition (or Square Root decomposition) is a technique used in programming to optimize evaluating some common queries on an array.
Some examples of common queries on an array are - finding the sum of elements of a given subarray, finding the maximum element in a given subarray, etc. These queries can be evaluated in O(N) time using the brute force approach as we have to traverse the complete subarray to get the answer. The time complexity of evaluating answers to these queries can be improved to O(sqrt(N)) using the sqrt decomposition technique.
The basic concept behind this technique is to divide the given array into small blocks of size ‘sqrt(N)’, precompute the desired results for these chunks and then evaluate the given queries using the precomputed results on the ‘sqrt(N)’ blocks.
Let’s see an example to understand this technique:
Suppose we have been given an array containing ‘N’ integers. Also, we have ‘Q’ queries, each of the form [L, R]. 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.
These queries can be evaluated with O(N) time complexity. Now, let’s see how we can evaluate these queries with O(sqrt(N)) time complexity using the ‘sqrt decomposition’ technique in the next section.
In this section, we will see how the queries of finding the sum of elements of a given subarray can be evaluated in O(sqrt(N)) time using the ‘sqrt decomposition’ technique.
The basic idea of sqrt decomposition is to decompose the given array into small blocks of size ‘√n’, where ‘n’ is the number of elements in the given array. If ‘n’ is a perfect then there will be a total of ‘√n’ blocks, else ‘√n + 1’ blocks. We will do the preprocessing and store the sum of elements of these blocks and use these precomputed results for evaluating queries in O(sqrt(N)) time.
Algorithm -
Step 1. First, declare three global variables - two global arrays ‘a[]’ and ‘blocks[]’ to store the given array and the precomputed sum of each block respectively, and an integer ‘blockSize’ to store the size of each block.
Step 2. Now create the function ‘preCompute()’ to divide the given array in the small blocks of size sqrt(n) and then to precompute the results. Inside the function, find the size of each block, store it in the globally declared variable ‘blockSize’ and then traverse the given array and store the sum of each block of size ‘sqrt(n)’ in the array ‘blocks[]’.
Step 3. Next, create the function ‘evaluateQueries()’ to evaluate queries for finding the sum of a given subarray using sqrt decomposition. Inside the function, declare a vector to store the answer of each query and then run a loop and call the function ‘findSum()’ to find the sum of the subarray of each query.
Step 4. Then, create the function ‘findSum()’ to find the sum of the subarray a[left, right] using sqrt decomposition. Inside the function, first calculate the sum of the first block in the range of the query, then find the sum of the blocks completely inside the range of the query and then sum of the last block inside the range of the query. Finally return the total sum.
Step 5. Finally, inside the main function, print the answer of each query which is stored in the vector returned by the function ‘evaluateQueries()’.
C++ code:
C++
C++
// 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 arr[] = {1, 2, 3, 4, 5, 6, 7}; int n = sizeof(arr)/sizeof(arr[0]);
// 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);
// Printing the answers for each Query for(int i=0; i<q; i++) { cout<<"Query "<<i+1<<": "<<ans[i]<<endl; }
return 0; }
Output:
Query 1: 14
Query 2: 25
Query 3: 15
Algorithm Complexity:
Time Complexity: O(Q * sqrt(N))
In the function “evaluateQueries()” for evaluating the queries to find the sum of elements less than or equal to a given number in a given subarray, “update()” and “query()” functions having time complexity of log(N), are called for each query. So, the overall time complexity is O(Q * log(N)), where ‘Q’ and 'N' are the number of queries and the number of elements in the array respectively.
Space Complexity: O(N)
In the function “evaluateQueries()” for evaluating the queries to find the number of elements less than or equal to a given number in a given subarray, we have created a vector 'bit' for Binary indexed tree, so the space complexity is O(N), where 'N' is the number of elements in the given array.
Range Query of type 1 (Given Range is on Block Boundaries)
This kind of query allows the range to encompass all continuous sqrt blocks. Therefore, the sum of values in this range can be readily found by adding the sum of the blocks that completely overlap.
Thus, ans = 11 + 15 = 26 will be the response to the above question in the given image.
O(sqrt(N)) is the time complexity. The worst-case scenario for our range is 0 to N-1, where N is the array's size and is assumed to be a perfect square. In this instance, our query range entirely overlaps every block. We must thus iterate through each of the array's deconstructed pieces in order to respond to this question, and we are aware that the total number of blocks is equal to sqrt(N). Therefore, in the worst scenario, the complexity of this kind of query will be O(sqrt(N)).
Range Query of type 2 (Given Range is NOT on boundaries):
To handle these kinds of queries, we first add up the values from the fully overlapped deconstructed blocks that are contained within the query range. Next, we add up the elements from the original array that correspond to blocks that are not entirely overlapped by the query range one by one.
Thus, ans = 5 + 2 + 11 + 3 = 21 will be the response to the above question in the described image.
The time complexity is O(sqrt(N)). Taking a look at the question [l = 1 and r = n-2] (n is the array's size; the indexing is 0-based). Because of this, the first and end blocks for this query will only have one element remaining outside of the overlapping range, while exactly (sqrt(n) – 2) blocks will overlap fully. Thus, the blocks that overlap entirely can be added up in (sqrt(n) – 2 ) ~ sqrt(n) repetitions, whereas the start and end blocks must be explored individually. To summarize, we must perform (sqrt(n)-1) ~ sqrt(n) iterations for each block, including the last one, as we know that the total number of items in each block is limited to sqrt(n).
The overall complexity is therefore equal to O(sqrt(n)) + O(sqrt(n)) + O(sqrt(n)) = O(3*sqrt(N)) = O(sqrt(N)).
Update Queries(Point update)
To execute the point update query, we first locate the block where the specified index resides, subtract its prior value, and then add the newly updated value.
Time Complexity is O(1).
Frequently Asked Questions
How the time complexity of evaluating range queries on an array is reduced using sqrt decomposition as compared to brute force approach?
To evaluate range queries using brute force approach, we traverse the complete range which leads to the time complexity of O(N). But, in the sqrt decomposition technique, we preprocess the given array, divide it into small blocks of size ‘√N’ and precompute the required result for each of the blocks and store it. Then , we use these precomputed results to evaluate the range queries on the array in O(sqrt(N)) time.
Conclusion
This article discussed the concept of “sqrt decomposition” and the solution of an example problem using “sqrt decomposition”, its C++ code, and its time and space complexity. If you want to solve more problems on data structure and algorithms for practice, you can visit Coding Ninjas Studio.
If you think that this blog helped you, then share it with your friends!. Refer to the DSA C++ course for more information.
305+ registered