1.
Introduction
2.
Problem Statement
3.
Approach
3.1.
Example
3.2.
Time Complexity
3.3.
Space Complexity
4.
Code in C++
5.
6.
Key Takeaways
Last Updated: Mar 27, 2024

Sqrt Decomposition Method

Gaurish Anand
0 upvote

Introduction

The sqrt decomposition method is an important method used by competitive programmers to solve problems efficiently. It helps in reducing the time complexity of query range problems.

We will understand this method by solving the famous range sum query method. Here is a link to the problem.

Problem Statement

Given an integer array, handle multiple queries of the following types:

1. Update Query: Update the element at an index in the array.
2. Sum Range Query: Find the sum of elements between the indices left and right.

Input format: Given a vector of integers and a 2D vector of integers. The ith row in the 2D vector represents the ith query, and on each row, we will have 3 integers:

1. Element at the 0th index of each row will represent the query type. If the element is 0, then it is an update query, and if the element is 1, then it is a sum range query.
2. If the query is an update query, the 2nd and 3rd elements will represent the index and the new value that needs to be updated at that index.
3. If the query is a sum range query, the 2nd and 3rd elements will represent the left index and the right index, respectively.

Input:
A[] = [10,1,9,2,6,4,3,5,8,7,21]
Queries : [[1,2,5], [0,3,101], [0,7,29], [1,1,7]]

Output: [21, null, null, 153]

Explanation:

1. Query 1:
Find the sum between the indexes [2,5]. Therefore the output is 21.
2. Query 2:
Update the element at the 3rd index to 101. Array after the update is [10,1,9,101,6,4,3,5,8,7,21].
3. Query 3:
Update the element at the 7th index to 29. Array after the update is [10,1,9,101,6,4,3,29,8,7,21].
4. Query 4:
Find the sum between the indexes [1,7]. Therefore the output is 153.

Approach

The most naive approach is updating the array's element in O(1) time and finding the sum looping over the range for each sum range query. But since the time complexity will be O(n) for every sum query, it is not an optimal solution.

2nd Method: We can also solve the above problem using segment trees. The time complexity, in this case, will be O(log N) for both the update and sum range queries. To learn more about the segment trees, you can go through this link.

3rd Method using sqrt decomposition technique: The time complexity, in this case, will be O(√N) for sum range queries and O(1) for the update queries.

The basic idea behind sqrt decomposition is to divide the array into blocks of length √N, and for each block, we will pre-compute the sum of all the block elements and store it in another array. For example,

1. Let’s assume we have an array of size n: a[0], a[1], a[2] …. a[n-2], a[n-1].
2. Let s = floor(√n) and ceil(n/s) = m.
3. Therefore, if we divide the array into blocks where the size of each block is s, then the number of blocks will be m, i.e., ceil(n/s).
Block 0: a[0], a[1], a[2] … a[s-1]
Block 1: a[s], a[s+1] … a[2s-1]
Block 2: a[2s], a[2s+1] … a[3s-1]
..
..
Block m-1: a[(m-1)s], a[(m-1)s+1] … a[n-1].
4. We will maintain the sum of each block in another array b[] where

Example

The array A[] = [10,1,9,2,6,4,3,5,8,7,21] of size = 11 will be decomposed into blocks of size floor(√11)= 3. Total number of blocks will be ceil(√11 / 3) = 4

Time Complexity

To initialize the blocks and the array b[k], we will execute O(n) operations. Now let’s discuss the time complexity in the case of the 2 query operations:

1. Update query - We need to find the block for the index that needs to be updated. Block number of an index i will be i/block_size. Therefore time complexity of the update operation is just O(1).
2. Sum range query - To calculate the sum in the range [left, right], we will need to calculate the sum of the whole blocks which are entirely included in the given range. This can be calculated in O(√N) time using the array b[]. The sum of the 2 cornered blocks, if they are partially included in the range [left, right], can be calculated by traversing on those blocks one by one in O(√N) time as we know the number of elements in a block is at most √N. Therefore the time complexity to calculate sum in a range will be to O(√N).

Space Complexity

Since we are making an auxiliary array b[] to store the sum of each block, the space complexity is O(√N), where N = size of the array.

Code in C++

``````#include<iostream>
#include<vector>
#include<cmath>
using namespace std;

vector<int> precomputeB(vector<int>& A,int block_size,int no_of_blocks){
vector<int> B;
for(int i=0;i<no_of_blocks;i++){
// To find the sum of the ith block, traverse from block_size*i to block_size*(i+1)-1
int sum = 0;
for(int j=block_size*i;j<block_size*(i+1);j++){
sum += A[j];
}
B.push_back(sum);
}
return B;
}

void update(vector<int>& A,int index,int new_value,int block_size,vector<int>& B){
int block_number = index / block_size;
B[block_number] = B[block_number] + new_value - A[index];
A[index] = new_value;
}
int sum(vector<int>& A,int l,int r,int block_size,vector<int>& B){
int sum = 0;
while(l<=r && l%block_size!=0){
sum += A[l];
l++;
}

// traversing entirely included blocks in the given range
while((l+block_size)<=r){
int block_index = l / block_size;
sum += B[block_index];
l = l + block_size;
}

// traversing the ending block if partially included in the range
while(l<=r){
sum += A[l];
l++;
}
return sum;
}
int main(){

vector<int> A = {10,1,9,2,6,4,3,5,8,7,21};
vector<vector<int> > queries = {{1,2,5}, {0,3,101}, {0,7,29}, {1,1,7}};

int N = A.size();
int block_size = floor(sqrt(N));
int no_of_blocks = ceil(N / double(block_size));

vector<int> B = precomputeB(A,block_size,no_of_blocks);

cout<<"The total numbers of blocks are "<<no_of_blocks<<endl;
cout<<"The size of each block is "<<block_size<<endl;

for(auto query:queries){
int query_type = query[0];
if(query_type==0){
update(A,query[1],query[2],block_size,B);
}else{
int l = query[1];
int r = query[2];
cout<<"The sum in the range ["<<l<<","<<r<<"] is: "<<sum(A,l,r,block_size,B)<<endl;
}
}
}``````

Output

``````The total numbers of blocks are 4
The size of each block is 3
The sum in the range [2,5] is: 21
The sum in the range [1,7] is: 153``````

1.What is a segment tree?

segment tree is a data structure used to store information about intervals or array segments. An array is used to represent it.

2.In what kind of problems can we use sqrt decomposition techniques?

We can use it when there are several range queries on an array and modifications of the array's elements. We should use this technique only when the number of update operations is more than the number of query range operations; otherwise, we can use segment trees.

3.Is there anything more in Coding Ninjas Studio that deals with Data Structures and Algorithms?

Yes, Coding Ninjas Studio offers both coding practice and frequently asked interview questions. The more we practice, the greater our chances of landing a job at our ideal organization.

Key Takeaways

In this article, we learned the importance of the sqrt decomposition method and its usefulness in optimizing query problems.
Check out this problem - Subarray Sum Divisible By K

Are you planning to ace the interviews of reputed product-based companies like Amazon, Google, Microsoft, and more? Attempt our Online Mock Test Series on Coding Ninjas Studio now!

Live masterclass