Sqrt (or Square Root) Decomposition Technique

You are given query of range an integer array. You will be asked to determine the sum of all the numbers that come in the range of given query. The query given is of two types, that are –

Update: (index, value) is given as a query, where you need to update the value of the array at position index with the ‘value’.

Sum: (left, right) is given a query, sum up all the numbers that come in the range.

Table of Contents

Example

Input

arr[] = {2,4,7,1,5,8,9,10,3,6}

Sum Query(0, 3)

Sum Query(4, 9)

Update(5, 8)

Sum Query(3, 7)

Output

14 ⇒ the sum of numbers within the range 0 and 3, is 14 (2 + 4 + 7 + 1)

41 ⇒ the sum of numbers within the range 4 and 9, is 41 (5 + 8 + 9 + 10 + 3 + 6)

Updating the value at array[5] as 8.

33 ⇒ the sum of numbers within the range 0 and 3, is 14 (1 + 5 + 8 + 9 + 10)

Algorithm

Get the square root value of n as a blocksize and traverse the array.
Copy the value of input array to the array we created and check if any of the indexes is divisible by blocksize if it then increases the value of blockindex by 1 and adds the value of arr[i] to the blockArray at blockindex.
To sum up the value in the given range, set the value of sum to 0.
Follow the three while loops, until the left is less than the value of the right, left should not be zero and left should not be the corner case of any block, then add the value of array[left] to the sum and increase the value of left.
In this, left plus blocksize should be less than the right, then add the value of blockArray at the index as the division of left and blocksize, and add the value of blocksize to the left.
In this, left is less than the right, add the value of array[left] to the sum and increase the value of left by 1, and return the value of the sum.
For any update query, get the division of index and blocksize, and add the value which was given to update and subtract the array[index]. At last update the ‘value’ at array[index].

Explanation

Square root decomposition is a technique to solve the questions to reduce the complexity in terms of the square root of sqrt(n). Given an array and the query range to find the sum of all the numbers which are in the given range of each query and another task is to update the value at the given index. So in this we are given some queries, and we need to solve that, we can solve it by using naïve approach. In that approach we will solve it by iterating over each element in the array within the given range of left and right, and sum all of the values present in range, but here for this approach time complexity for each approach will be O(n).

So to optimize the queries most efficiently, we will use square root decomposition, helping us to reduce the time complexity. We can assume that an array of size n consisting n elements. We will divide the array into small chunks or blocks of size sqrt(n). for every perfect square as a number, we will have precise sqrt(n) chunks. With this decomposition of the array, we will have sqrt(n) blocks and in each block. We will be having sqrt(n) elements if n is a perfect square, where n is a size of an array.

Suppose we have an sqrt(16) blocks since 16 is a perfect square. We will have exactly 4 blocks and each block will be containing exactly 4 elements. Each block we will have the sum of all the elements lying in each block. So if we ask to find out the sum of any range query. We can easily find the sum by using blocks sum.

Implementation in C++ for Sqrt (or Square Root) Decomposition Technique

#include<iostream>
#include<math.h>

using namespace std;


int arr[10000];
int blockArray[100];
int blockSize;

void buildArray(int input[], int n)
{
    int blockIndex = -1;

    blockSize = sqrt(n);

    for (int i=0; i<n; i++)
    {
        arr[i] = input[i];
        if (i%blockSize == 0)
        {
            blockIndex++;
        }
        blockArray[blockIndex] += arr[i];
    }
}

void update(int index, int value)
{
    int blockNumber = index / blockSize;
    blockArray[blockNumber] += value - arr[index];
    arr[index] = value;
}

int solveQuery(int left, int right)
{
    int sum = 0;
    while (left<right and left%blockSize!=0 and left!=0)
    {
        sum += arr[left];
        left++;
    }
    while (left+blockSize <= right)
    {
        sum += blockArray[left/blockSize];
        left += blockSize;
    }
    while (left<=right)
    {
        sum += arr[left];
        left++;
    }
    return sum;
}

int main()
{
    int inputArray[] = {2,4,7,1,5,8,9,10,3,6};
    int n = sizeof(inputArray)/sizeof(inputArray[0]);

    buildArray(inputArray, n);

    cout << "first Query : " << solveQuery(0, 3) << endl;
    cout << "second Query : " << solveQuery(4, 9) << endl;
    update(5, 8);
    cout << "third Query : " << solveQuery(3, 7) << endl;
    return 0;
}

first Query : 14
second Query : 41
third Query : 33

Implementation in Java for Sqrt (or Square Root) Decomposition Technique

class SquareRootDecomposition
{

    static int []arr = new int[10000];
    static int []blockArray = new int[100];
    static int blockSize;

    static void buildArray(int input[], int n)
    {
        int blockIndex = -1;

        blockSize = (int) Math.sqrt(n);

        for (int i = 0; i < n; i++)
        {
            arr[i] = input[i];
            if (i % blockSize == 0)
            {
                blockIndex++;
            }
            blockArray[blockIndex] += arr[i];
        }
    }

    static void update(int idx, int val)
    {
        int blockNumber = idx / blockSize;
        blockArray[blockNumber] += val - arr[idx];
        arr[idx] = val;
    }

    static int solveQuery(int left, int right)
    {
        int sum = 0;
        while (left<right && left%blockSize!=0 && left!=0)
        {
            sum += arr[left];
            left++;
        }
        while (left+blockSize <= right)
        {
            sum += blockArray[left/blockSize];
            left += blockSize;
        }
        while (left<=right)
        {
            sum += arr[left];
            left++;
        }
        return sum;
    }

    public static void main(String[] args)
    {
        int input[] = {2,4,7,1,5,8,9,10,3,6};
        int n = input.length;

        buildArray(input, n);

        System.out.println("first Query: " + solveQuery(0, 3));
        System.out.println("second Query : " + solveQuery(4, 9));
        update(5, 8);
        System.out.println("third Query : " + solveQuery(3, 7));
    }
}

first Query: 14
second Query : 41
third Query : 33