Learn Sparse Table — Free DSA Tutorial

What is Sparse Table

A sparse table preprocesses a fixed, unchanging array once so that later range queries — like whats the minimum value between index 3 and index 9' — can be answered almost instantly, at the cost of some extra memory and a one-time setup pass.

Example: What is Sparse Table

#include <iostream>
using namespace std;
int main() {
	cout << "Preprocess a fixed array once, answer range-minimum-style queries almost instantly afterward";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Preprocess a fixed array once, answer range-minimum-style queries almost instantly afterward");
	}
}

print("Preprocess a fixed array once, answer range-minimum-style queries almost instantly afterward")

#include <stdio.h>
int main() {
	printf("Preprocess a fixed array once, answer range-minimum-style queries almost instantly afterward");
	return 0;
}

Preprocessing

During preprocessing, the table stores precomputed answers for every range whose length is a power of two, starting from single-element ranges and doubling the range length at each successive level.

Example: Preprocessing

#include <iostream>
using namespace std;
int main() {
	int arr[] = {2,4,1,7,3,9,8};
	int sparse[3][7];
	for (int i = 0; i < 7; i++) sparse[0][i] = arr[i];
	for (int i = 0; i + 1 < 7; i++) sparse[1][i] = min(sparse[0][i], sparse[0][i+1]);
	cout << "Range length 2 starting at 0 (power of two): min = " << sparse[1][0];
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int[] arr = {2,4,1,7,3,9,8};
		int[][] sparse = new int[3][7];
		for (int i = 0; i < 7; i++) sparse[0][i] = arr[i];
		for (int i = 0; i + 1 < 7; i++) sparse[1][i] = Math.min(sparse[0][i], sparse[0][i+1]);
		System.out.println("Range length 2 starting at 0 (power of two): min = " + sparse[1][0]);
	}
}

arr = [2,4,1,7,3,9,8]
sparse = [[0]*7 for _ in range(3)]
sparse[0] = arr[:]
for i in range(6):
    sparse[1][i] = min(sparse[0][i], sparse[0][i+1])
print("Range length 2 starting at 0 (power of two): min =", sparse[1][0])

#include <stdio.h>
int main() {
	int arr[] = {2,4,1,7,3,9,8};
	int sparse[3][7];
	for (int i = 0; i < 7; i++) sparse[0][i] = arr[i];
	for (int i = 0; i+1 < 7; i++) sparse[1][i] = sparse[0][i] < sparse[0][i+1] ? sparse[0][i] : sparse[0][i+1];
	printf("Range length 2 starting at 0 (power of two): min = %d", sparse[1][0]);
	return 0;
}

Range Minimum Query

For operations where overlapping two ranges twice doesn't change the answer — like minimum, maximum, or GCD — any arbitrary range can be covered by just two overlapping power-of-two ranges from the table, answered in O(1) after preprocessing.

Example: Range Minimum Query

#include <iostream>
using namespace std;
int main() {
	int arr[] = {2,4,1,7,3,9,8};
	int sparse0[7], sparse1[7], sparse2[7];
	for (int i = 0; i < 7; i++) sparse0[i] = arr[i];
	for (int i = 0; i+1 < 7; i++) sparse1[i] = min(sparse0[i], sparse0[i+1]);
	for (int i = 0; i+3 < 7; i++) sparse2[i] = min(sparse1[i], sparse1[i+2]);
	cout << "Range [0,3] covered by two overlapping length-2 ranges, min = " << min(sparse1[0], sparse1[2]);
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int[] arr = {2,4,1,7,3,9,8};
		int[] s0 = new int[7], s1 = new int[7];
		for (int i = 0; i < 7; i++) s0[i] = arr[i];
		for (int i = 0; i+1 < 7; i++) s1[i] = Math.min(s0[i], s0[i+1]);
		System.out.println("Range [0,3] covered by two overlapping length-2 ranges, min = " + Math.min(s1[0], s1[2]));
	}
}

arr = [2,4,1,7,3,9,8]
s0 = arr[:]
s1 = [min(s0[i], s0[i+1]) for i in range(6)]
print("Range [0,3] covered by two overlapping length-2 ranges, min =", min(s1[0], s1[2]))

#include <stdio.h>
int main() {
	int arr[] = {2,4,1,7,3,9,8};
	int s0[7], s1[7];
	for (int i = 0; i < 7; i++) s0[i] = arr[i];
	for (int i = 0; i+1 < 7; i++) s1[i] = s0[i] < s0[i+1] ? s0[i] : s0[i+1];
	int result = s1[0] < s1[2] ? s1[0] : s1[2];
	printf("Range [0,3] covered by two overlapping length-2 ranges, min = %d", result);
	return 0;
}

Limitations

Because the table is built once from the original array and never updated, sparse tables aren't suitable for problems where array values change over time; a segment tree is the better fit whenever updates are needed.

Example: Limitations

#include <iostream>
using namespace std;
int main() {
	cout << "Built once from the original array -- not suitable if array values change; use a segment tree instead";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Built once from the original array -- not suitable if array values change; use a segment tree instead");
	}
}

print("Built once from the original array -- not suitable if array values change; use a segment tree instead")

#include <stdio.h>
int main() {
	printf("Built once from the original array -- not suitable if array values change; use a segment tree instead");
	return 0;
}

Applications

Sparse tables shine specifically when the array is fixed but you need to answer a huge number of range queries against it — the one-time preprocessing cost quickly pays for itself compared to scanning each range from scratch.

Example: Applications

#include <iostream>
using namespace std;
int main() {
	cout << "Fixed array, huge number of range queries -- one-time preprocessing quickly pays for itself";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Fixed array, huge number of range queries -- one-time preprocessing quickly pays for itself");
	}
}

print("Fixed array, huge number of range queries -- one-time preprocessing quickly pays for itself")

#include <stdio.h>
int main() {
	printf("Fixed array, huge number of range queries -- one-time preprocessing quickly pays for itself");
	return 0;
}

Sparse Table

What is Sparse Table

Preprocessing

Range Minimum Query

Limitations

Applications

Chapter Quiz — Complete all 7 topics to unlock

Login to run this code