Range Sum Query using Sparse Table

Difficulty Level Medium
Frequently asked in Amazon Publicis Sapient Zoho
ArrayViews 2219

In the range sum query using sparse table problem we have a range query and given an integer array. The given task is to find out the sum of all integers that comes in the range.

Example

Input:

arr[] = {1,4,6,8,2,5}

Query: {(0, 3), (2, 4), (1, 5)}

Output:

19 16 25

Explanation: The sum of integers that comes in range 0, 3 inclusively is 1 + 4 + 6 + 8 is 19. Again, the sum of integers that comes in range 2, 4 inclusively is 6 + 8 + 2 is 16. The sum of integers that comes in range 1, 5 inclusively is 4 + 6 + 8 + 2 + 5 is 25.

Range Sum Query using Sparse Table

Algorithm

  1. Build a sparse table using a 2d matrix.
  2. Traverse the array and mark every row of the sparse_table to array[i].
  3. Traverse the array nestedly, and update the value sparse_table as the sum of the sparse table of previous column and at the sparse_table[i+2 j-1 ][j-1] and store it to sparse_table[i][j].
  4. For each query to solve, we get left and right, set the value of output to 0.
  5. Traverse the array from 16 to 0, and check if the left + 2j -1 is less than is equal to right, if true,
    1. Add the value of output to sparse_table[left][j] and store the sum into output.
    2. Update the value of left to left + 2
  6. Return the value of output.

Explanation for Range Sum Query using Sparse Table

Given an array and a query. Find out the sum of all the integers that comes within a range in a query. We will be using the sparse table concept. We will be building a sparse table. The sparse table is a 2d matrix in which we are going to perform some operations and store the values in a sparse table.

Declare a 2d matrix. We have taken a limit of one lakh rows and maximum of 16 columns each. We have particularly taken a number 16 here because after that we will get a number which is greater than 2 raised to the power 5, so 16 is enough. Then after will get on to the first stage of building a sparse table. We are going to mark or update the values at the sparse table as the given array element while traversing through the array. Then nested we are going to traverse the array, again up to k number of rows. Update the sparse table at i, j as the sum of the sparse table at i, j-1 and the sparse table at i+2j-1, j-1. This will be final required updation for the sparse table.

For each query given as left, right range, we need to traverse the array, but before that set the value of output to 0. Traverse the array from 16 to 0, so that we can get the powers in terms of 2, each time 1<<j will represent the number in powers of 2, we will check if the sum of the 2j-1 +left is equal to right, then update the value of output by the sum of output and sparse table at left, j and simultaneously update the value of left to the sum of left and powers of 2^j. finally, return the value of output.

Implementation

C++ program for Range Sum Query using Sparse Table

#include<iostream>

using namespace std;

const int k = 16;

const int N = 1e5;

long long sparse_table[N][k + 1];

void SparseTable(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        sparse_table[i][0] = arr[i];

    for (int j = 1; j <= k; j++)
        for (int i = 0; i <= n - (1 << j); i++)
            sparse_table[i][j] = sparse_table[i][j - 1] +
                                 sparse_table[i + (1 << (j - 1))][j - 1];
}

long long solveQuery(int Left, int Right)
{
    long long output = 0;
    for (int j = k; j >= 0; j--)
    {
        if (Left + (1 << j) - 1 <= Right)
        {
            output = output + sparse_table[Left][j];

            Left += 1 << j;
        }
    }
    return output;
}

int main()
{
    int arr[] = { 1,4,6,8,2,5 };
    int n = sizeof(arr) / sizeof(arr[0]);

    SparseTable(arr, n);

    cout << solveQuery(0, 3) << endl;
    cout << solveQuery(2, 4) << endl;
    cout << solveQuery(1, 5) << endl;

    return 0;
}
19
16
25

Java program for Range Sum Query using Sparse Table

class SumQueryRange
{
    static int k = 16;

    static int N = 100000;

    static long sparse_table[][] = new long[N][k + 1];

    static void SparseTable(int arr[],int n)
    {
        for (int i = 0; i < n; i++)
            sparse_table[i][0] = arr[i];

        for (int j = 1; j <= k; j++)
            for (int i = 0; i <= n - (1 << j); i++)
                sparse_table[i][j] = sparse_table[i][j - 1] + sparse_table[i + (1 << (j - 1))][j - 1];
    }
    
    static long solveQuery(int Left, int Right)
    {
        long sol = 0;
        for (int j = k; j >= 0; j--)
        {
            if (Left + (1 << j) - 1 <= Right)
            {
                sol = sol + sparse_table[Left][j];

                Left += 1 << j;
            }
        }
        return sol;
    }
    
    public static void main(String args[])
    {
        int arr[] = { 1,4,6,8,2,5};
        int n = arr.length;

        SparseTable(arr, n);

        System.out.println(solveQuery(0, 3));
        System.out.println(solveQuery(2, 4));
        System.out.println(solveQuery(1, 5));
    }
}

19
16
25

Complexity Analysis

Time Complexity

O(n * log(n)) where “n” is the number of elements in the array.

Space Complexity

O(n * log(n)) where “n” is the number of elements in the array.

Reference

Translate »