Square Root (Sqrt) Decomposition Algorithm Using Brute force
- In this approach, we simply iterate over each element in the range l to r and calculate its corresponding answer.
- Let’s consider these chunks or blocks as an individual array each of which contains sqrt(N) elements and you have computed your desired answer(according to your problem) individually for all the chunks.
- Now, you need to answer certain queries asking you the answer for the elements in the range l to r(l and r are starting and ending indices of the array) in the original n-sized array.
- Simply iterate over each element in the range l to r calculate its sum and return it for an answer.
Example:
Javascript
const MAXN = 20000; const arr = []; // Function for sqrt decomposition function query(l, r) { let sum = 0; for (let i = l; i <= r; i++) { sum += arr[i]; } return sum; } // Driver code function main() { const input = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]; const n = input.length; arr.push(...input); console.log("query(3,8) : ", query(3, 8)); console.log("query(1,6) : ", query(1, 6)); arr[5] = 0; console.log("query(6,6) : ", query(6, 6)); } main(); |
Output
query(3,8) : 27 query(1,6) : 39 query(6,6) : 4
Time Complexity: O(N)
We can deal with these types of queries by summing the data from the completely
overlapped decomposed blocks lying in the query range and then summing elements one
by one from the original array whose corresponding block is not completely overlapped by the query range.
So the answer for the above query in the described image will be: ans = 5 + 2 + 11 + 3 = 21
Square Root (Sqrt) Decomposition Algorithm Using JavaScript Array
In this article, we are going to learn how we can use the Square Root (Sqrt) Decomposition Algorithm using a JavaScript array. The square Root Decomposition Technique is one of the most common query optimization techniques used by competitive programmers. This technique helps us to reduce Time Complexity by a factor of sqrt(N).
Approaches for Square Root (Sqrt) Decomposition Algorithm:
- Brute force
- Efficient approach