Sqrt Decomposition Method

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

Frequently Asked Questions

1.What is a segment tree?

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