Introduction
A Sparse Table is a powerful data structure used for solving Range Queries efficiently when updates are not required. It excels at answering idempotent queries (queries where repeated application does not change the result), such as Range Minimum Query (RMQ), Range Maximum Query (RMaxQ), and Greatest Common Divisor (GCD) queries.
This blog will cover:
1. What is a Sparse Table?
2. How does it work?
3. Building the Sparse Table
4. Querying the Sparse Table
5. Time and Space Complexity
6. Fantastic Examples
7. Comparison with Segment Tree
By the end, you'll have a deep understanding of Sparse Tables and how to implement them in competitive programming!
Understanding the Sparse Table
A Sparse Table is a precomputed data structure that allows answering range queries in O(1) time after an O(N log N) preprocessing step. It is ideal for static arrays where elements don't change after preprocessing.
####
When to Use Sparse Table?
1. When the problem involves static range queries (no updates).
2. When the operation is idempotent (e.g., min, max, GCD).
3. When you need fast queries in O(1) time.
4. When you can afford O(N log N) preprocessing time and O(N log N) space.
####
How Does the Sparse Table Work?
The Sparse Table stores precomputed answers for overlapping subarrays of power-of-two lengths. Using this precomputed information, we can answer queries in constant time.
We define st[i][j], where:
1. i represents the starting index of the range.
2. j represents the length of the subarray as 2^j (powers of two).
For example, if j = 3, the range size is 2^3 = 8, meaning st[i][3] stores the result for the range [i, i + 7].
####
Building the Table
We fill st[i][j] based on the idempotent property:
st[i][j]=operation(st[i][j−1],st[i+2^j−1][j−1])
This formula ensures that every interval is built using two smaller, previously computed intervals.
Implementation of Sparse Table (Range Minimum Query)
Let's now implement a Sparse Table for Range Minimum Query (RMQ).
class SparseTable { constructor(arr) { this.n = arr.length; this.log = new Uint8Array(this.n + 1); this.st = Array.from({ length: this.n }, () => new Int32Array(20));
// Compute logarithm values
for (let i = 2; i <= this.n; i++) this.log[i] = this.log[i >> 1] + 1;
// Initialize Sparse Table with original array values
for (let i = 0; i < this.n; i++) this.st[i][0] = arr[i];
// Fill the table
for (let j = 1;
(1 << j) <= this.n; j++) {
for (let i = 0; i + (1 << j) <= this.n; i++) {
this.st[i][j] = Math.min(this.st[i][j - 1], this.st[i + (1 << (j - 1))][j - 1]);
}
}
}
// Query for minimum in range [L, R]
query(L, R) {
let j = this.log[R - L + 1];
return Math.min(this.st[L][j], this.st[R - (1 << j) + 1][j]);
}}
// Usage let arr = [1, 3, 5, 7, 9, 2, 6, 4, 8, 0]; let st = new SparseTable(arr); console.log(st.query(2, 5)); // Output: 2 console.log(st.query(0, 9)); // Output: 0
Querying the Sparse Table
==============================
For a given range [L, R], we use the largest power of two segment that fits within the range. This means:
answer=min(st[L][j],st[R−2^j+1][j])
where:
j=floor(log(R−L+1))
We use two overlapping intervals to cover the entire range.
Why Does Querying Take O(1) ?
Since we're only performing two lookups and a Math.min() operation, the time complexity is O(1).
Space and Time Complexity
Operation
Building Table => O(n log n)
Querying => O(1)
Space Complexity => O(n log n)
Sparse Table is extremely efficient for static range queries but is not suitable for problems requiring modifications.
Examples of Sparse Table in Action
Example 1: Range Maximum Query
We replace Math.min() with Math.max(), and the implementation remains the same.
Example 2: Range GCD Query
Instead of min/max, we use gcd(a, b):
function gcd(a, b) { while (b)[a, b] = [b, a % b]; return a; }
Then, replace Math.min() in st[i][j] computation with gcd().
Segment Tree vs. Sparse Table
Feature
Preprocessing Time => O(n log n)(sparse Table) => O(n)(Segment Tree)
Query Time => O(1)(sparse Table) => O(log n)(Segment Tree)
Update Time => Not Possible(sparse Table) => O(log n)(Segment Tree)
Space Complexity => O(n log n)(sparse Table) => O(n)(Segment Tree)
Sparse Tables win when:
You have static data (no updates).
You need fast queries (O(1) vs. O(log N) in Segment Tree).
Conclusion
Sparse Tables are super-efficient for answering range queries when updates are not needed. By precomputing power-of-two segments, we ensure queries can be answered in constant time.
Key Takeaways:
Precompute in O(n log n), Query in O(1).
####
Works only for idempotent operations like min, max, GCD.
####
Not suitable for problems requiring updates.
####
Better than Segment Tree for static queries.
Try implementing Sparse Tables for different problems like:
1. LCM Queries
2. Bitwise AND Queries
3. Sum Queries (with a slight tweak)
By mastering Sparse Tables, you unlock a powerful technique for fast range queries in competitive programming!
Happy Coding!
=============
