Sparse Table Construction (SUM QRY)

Approach

As the title of this article itself suggests we will be using the concept of sparse table to solve the problem. Let’s first see how a sparse table is constructed from a given array.

Construction of Sparse Table

The main intuition behind sparse table representation comes from the binary representation of an integer. As any integer can have its unique binary representation, it can be expressed as the sum of powers of 2. So, any interval or range can be expressed as the sum of decreasing powers of 2.

We will precompute the sum of the ranges having the length of power of 2 from each index of the given array. To answer queries efficiently we will use these precomputed values.

To store these precomputed values we will use a 2D array known as the sparse table of size n*(k+1) where n is the length of the given array and k=logn (of base 2).

For any sparse table st, st[i][j] will store the sum of the range [ i to  i+2j-1] that is of length 2j.

range [i,  i+2j-1] can be broken into two ranges [i, i+2j-1-1] and [ i+2j-1,  i+2j-1] of length  2j-1.So, st[i][j] can be expressed as 

st[ i][ j] = st[ i ][ j-1] + st[ i+2j-1] [  j-1]

//constructing the sparse table.
int st[n][k+1];

for(int i=0;i<n;i++)
{
	st[i][0]=arr[i];
}

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

For answering the given range sum query [l,r] we will try to split the range into lengths of powers of 2 starting from the largest possible value k. If the first split is the range [l, l+2j-1] i.e. st[ l, j], we will try to split the remaining range [l+2j, r] in the same way.

//answering range sum query (l,r)
int    query(int l,int r)
{
    int sum=0;

	for(int j=k;j>=0;j--)
	{
		if((1<<j)<=r-l+1)
		{
		sum+=st[l][j];
		l+=1<<j;
		}
	}
 return sum;
}    

Code

//C++ implementation of constrcuting Sparse Table 

#include<bits/stdc++.h>
using namespace std;

//driver code

int main()
{
	int n=6;
	int arr[] = { 2, 4, 3, 5, 7, 9 };

	//constructing Sparse Table
	int k=log(n)/log(2);

	int st[n][k+1];

	for(int i=0;i<n;i++)
	{
  		st[i][0]=arr[i];
	}

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

	//answering query (l,r)
    int l=0,r=2;
    
	int sum=0;

	for(int j=k;j>=0;j--)
	{
		if((1<<j)<=r-l+1)
		{
			sum+=st[l][j];
			l+=1<<j;
		}
	}

	cout<<"Range sum for the given query: " << sum;
}

You can also try this code with Online C++ Compiler

Run Code

Output

Range sum for the given query: 9

You can also try this code with Online C++ Compiler

Run Code

Complexity analysis

The Time Complexity of constructing a sparse table is O(n*k) ≅ O(n*logn) and answering a single query takes O(k)≅ O(logn) where n is the size of the given array.

Space complexity is O(n*logn).

FAQs

1. What is the Sparse Table?
   Sparse Table is a special kind of data structure to answer range queries on an array efficiently. It is implemented as a 2d array.
    
2. In which type of problem Sparse Table can be used?
   To perform range queries on any static data set, the sparse table is used.

Key Takeaways

This article covered the construction of a sparse table and how to solve the range sum queries using the sparse table.

Recommended Readings:

• Binary Search
• Dynamic Programming
• Book Allocation Problem
• Plates Between Candles
• Find the subarray with t
   

Check out the Coding Ninjas Studio library for getting a better hold of the data structures and algorithms.
Side by side, you can also practice a wide variety of coding questions commonly asked in interviews in Coding Ninjas Studio. Along with coding questions, you can also find the interview experience of scholars working in renowned product-based companies here. 

Happy learning!