Efficient approach

Square Root (Sqrt) Decomposition Algorithm Using Brute force

In this approach, we simply find the block in which the given index lies, then subtract its previous value and add the new updated value as per the point update query.
We have constructed the decomposed array of sqrt(N) blocks and now we need to print the sum of elements in a given range.
The range may totally cover the continuous sqrt blocks. So we can easily answer the sum of values in this range as the sum of completely overlapped blocks.

Example:

Javascript

let MAXN = 10000; 
let SQRSIZE = 100; 
  
let arr = new Array(MAXN); 
for (let i = 0; i < MAXN; i++) { 
    arr[i] = 0; 
} 
  
let block = new Array(SQRSIZE); 
for (let i = 0; i < SQRSIZE; i++) { 
    block[i] = 0; 
} 
  
let x; 
  
// Function for updating value  
// at specific index 
// of an array 
function update(idx, val) { 
    let blockNumber = idx / x; 
    block[blockNumber] += val - arr[idx]; 
    arr[idx] = val; 
} 
function query(l, r) { 
    let sum = 0; 
    while (l < r && l % x != 0 && l != 0) { 
        // traversing first block in range 
        sum += arr[l]; 
        l++; 
    } 
    while (l + x - 1 <= r) { 
      
        // Traversing completely 
        // overlapped blocks in range 
        sum += block[l / x]; 
        l += x; 
    } 
    while (l <= r) { 
        // Traversing last block in range 
        sum += arr[l]; 
        l++; 
    } 
    return sum; 
} 
  
// Fills values in input[] 
function preprocess(input, n) { 
  
    // Initiating block pointer 
    let x = -1; 
  
    // Calculating size of block 
    x = Math.floor(Math.sqrt(n)); 
  
    // Building the decomposed array 
    for (let i = 0; i < n; i++) { 
        arr[i] = input[i]; 
        if (i % x == 0) { 
  
            // Entering next block 
            // Incrementing block pointer 
            x++; 
        } 
        block[x] += arr[i]; 
    } 
} 
  
let input = [1, 5, 2, 4, 6, 1, 3, 5, 7, 10]; 
let n = input.length; 
  
preprocess(input, n); 
  
console.log("query(3,7) : " + 
    query(3, 7)); 
console.log("query(4,4) : " + 
    query(4, 4)); 
update(6, 0); 
console.log("query(5,5) : " + 
    query(5, 5));

Output

query(3,7) : 19
query(4,4) : 6
query(5,5) : 1

Time Complexity: O(sqrt(N))

Auxiliary Space: O(MAXN), since MAXN extra space has been taken, where MAXN is the maximum value of N

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

Tags:

#javascript-array #JavaScript-DSA #JavaScript-Program #JavaScript #Web Technologies

Square Root (Sqrt) Decomposition Algorithm Using Brute force

Efficient approach

Javascript

Square Root (Sqrt) Decomposition Algorithm Using JavaScript Array

Similar Reads

Contact Us