Tutorialspoint.dev

Range sum query using Sparse Table

We have an array arr[]. We need to find the sum of all the elements in the range L and R where 0 <= L <= R <= n-1. Consider a situation when there are many range queries.

Examples:

Input : 3 7 2 5 8 9
        query(0, 5)
        query(3, 5)
        query(2, 4)
Output : 34
         22
         15

Note : array is 0 based indexed
       and queries too.



Since there are no updates/modifications, we use Sparse table to answer queries efficiently. In sparse table, we break queries in powers of 2.

Suppose we are asked to compute sum of 
elements from arr[i] to arr[i+12]. 
We do the following:

// Use sum of 8 (or 23) elements 
table[i][3] = sum(arr[i], arr[i + 1], ...
                               arr[i + 7]).

// Use sum of 4 elements
table[i+8][2] = sum(arr[i+8], arr[i+9], ..
                                arr[i+11]).

// Use sum of single element
table[i + 12][0] = sum(arr[i + 12]).

Our result is sum of above values.

Notice that it took only 4 actions to compute result over subarray of size 13.

C++

// CPP program to find the sum in a given
// range in an array using sparse table.
#include <bits/stdc++.h>
using namespace std;
  
// Because 2^17 is larger than 10^5
const int k = 16;
  
// Maximum value of array
const int N = 1e5;
  
// k + 1 because we need to access
// table[r][k]
long long table[N][k + 1];
  
// it builds sparse table.
void buildSparseTable(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        table[i][0] = arr[i];
  
    for (int j = 1; j <= k; j++)
        for (int i = 0; i <= n - (1 << j); i++)
            table[i][j] = table[i][j - 1] +
               table[i + (1 << (j - 1))][j - 1];
}
  
// Returns the sum of the elements in the range
// L and R.
long long query(int L, int R)
{
    // boundaries of next query, 0-indexed
    long long answer = 0;
    for (int j = k; j >= 0; j--) {
        if (L + (1 << j) - 1 <= R) {
            answer = answer + table[L][j];
  
            // instead of having L', we
            // increment L directly
            L += 1 << j;
        }
    }
    return answer;
}
  
// Driver program.
int main()
{
    int arr[] = { 3, 7, 2, 5, 8, 9 };
    int n = sizeof(arr) / sizeof(arr[0]);
  
    buildSparseTable(arr, n);
  
    cout << query(0, 5) << endl;
    cout << query(3, 5) << endl;
    cout << query(2, 4) << endl;
  
    return 0;
}

Java

// Java program to find the sum 
// in a given range in an array 
// using sparse table.
class GFG
{
      
// Because 2^17 is larger than 10^5
static int k = 16;
  
// Maximum value of array
static int N = 100000;
  
// k + 1 because we need
// to access table[r][k]
static long table[][] = new long[N][k + 1];
  
// it builds sparse table.
static void buildSparseTable(int arr[],
                             int n)
{
    for (int i = 0; i < n; i++)
        table[i][0] = arr[i];
  
    for (int j = 1; j <= k; j++)
        for (int i = 0; i <= n - (1 << j); i++)
            table[i][j] = table[i][j - 1] +
            table[i + (1 << (j - 1))][j - 1];
}
  
// Returns the sum of the 
// elements in the range L and R.
static long query(int L, int R)
{
    // boundaries of next query,
    // 0-indexed
    long answer = 0;
    for (int j = k; j >= 0; j--) 
    {
        if (L + (1 << j) - 1 <= R) 
        {
            answer = answer + table[L][j];
  
            // instead of having L', we
            // increment L directly
            L += 1 << j;
        }
    }
    return answer;
}
  
// Driver Code
public static void main(String args[])
{
    int arr[] = { 3, 7, 2, 5, 8, 9 };
    int n = arr.length;
  
    buildSparseTable(arr, n);
  
    System.out.println(query(0, 5));
    System.out.println(query(3, 5));
    System.out.println(query(2, 4));
}
}
  
// This code is contributed 
// by Kirti_Mangal

C#

// C# program to find the 
// sum in a given range
// in an array using
// sparse table.
using System;
  
class GFG
{
    // Because 2^17 is
    // larger than 10^5
    static int k = 16;
      
    // Maximum value 
    // of array
    static int N = 100000;
      
    // k + 1 because we 
    // need to access table[r,k]
    static long [,]table = 
           new long[N, k + 1];
      
    // it builds sparse table.
    static void buildSparseTable(int []arr, 
                                 int n)
    {
        for (int i = 0; i < n; i++)
            table[i, 0] = arr[i];
      
        for (int j = 1; j <= k; j++)
            for (int i = 0;     
                     i <= n - (1 << j); i++)
                table[i, j] = table[i, j - 1] +
                table[i + (1 << (j - 1)), j - 1];
    }     
      
    // Returns the sum of the
    // elements in the range
    // L and R.
    static long query(int L, int R)
    {
        // boundaries of next 
        // query, 0-indexed
        long answer = 0;
        for (int j = k; j >= 0; j--) 
        {
            if (L + (1 << j) - 1 <= R) 
            {
                answer = answer + 
                         table[L, j];
      
                // instead of having 
                // L', we increment 
                // L directly
                L += 1 << j;
            }
        }
        return answer;
    }
      
    // Driver Code
    static void Main()
    {
        int []arr = new int[]{3, 7, 2, 
                              5, 8, 9};
        int n = arr.Length;
      
        buildSparseTable(arr, n);
      
        Console.WriteLine(query(0, 5));
        Console.WriteLine(query(3, 5));
        Console.WriteLine(query(2, 4));
    }
}
  
// This code is contributed by 
// Manish Shaw(manishshaw1)

Output:

34
22
15

This algorithm for answering queries with Sparse Table works in O(k), which is O(log(n)), because we choose minimal k such that 2^k+1 > n.

Time complexity of sparse table construction : Outer loop runs in O(k), inner loop runs in O(n). Thus, in total we get O(n * k) = O(n * log(n))



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter