Implementing Sparse Table Pattern
1. Building Sparse Table Technique
The Sparse Table is a data structure that allows for efficient range queries, particularly range minimum/maximum queries. It pre-processes the input array to answer queries in O(1) time after O(n log n) preprocessing.
| Operation | Description | Time Complexity |
|---|---|---|
| Preprocessing | Builds a 2D table where table[i][j] stores the minimum/maximum in range [i, i + 2^j - 1] |
O(n log n) |
| Query | Answer range queries using precomputed values | O(1) |
Example: Building Sparse Table for Range Minimum Query
function buildSparseTable(arr) {
const n = arr.length;
const k = Math.floor(Math.log2(n));
const table = Array(n).fill(0).map(() => Array(k + 1).fill(0));
// Initialize table with single elements
for (let i = 0; i < n; i++) {
table[i][0] = arr[i];
}
// Build the sparse table
for (let j = 1; j <= k; j++) {
for (let i = 0; i + (1 << j) <= n; i++) {
table[i][j] = Math.min(table[i][j - 1], table[i + (1 << (j - 1))][j - 1]);
}
}
return table;
}
function rangeMinQuery(table, L, R) {
const k = Math.floor(Math.log2(R - L + 1));
return Math.min(table[L][k], table[R - (1 << k) + 1][k]);
}
// Example usage:
const arr = [1, 3, 2, 7, 9, 11];
const sparseTable = buildSparseTable(arr);
console.log(rangeMinQuery(sparseTable, 1, 4)); // Output: 2
Note: The Sparse Table is ideal for static arrays where queries are frequent and updates are rare. It's particularly useful in competitive programming and algorithmic challenges.
2. Constructing Sparse Table
A sparse table is a data structure that allows for efficient range queries on an array. It precomputes results for all possible ranges of sizes that are powers of two, enabling fast query responses.
| Operation | Description | Time Complexity | Space Complexity |
|---|---|---|---|
| Preprocessing | Builds the sparse table by computing values for ranges of size 2^j | O(n log n) |
O(n log n) |
| Query | Retrieves the result for a given range [L, R] | O(1) |
O(1) |
Example: Building a Sparse Table for Range Minimum Query
function buildSparseTable(arr) {
const n = arr.length;
const k = Math.floor(Math.log2(n));
const table = Array(n).fill().map(() => Array(k + 1).fill(0));
// Initialize base case (range size = 1)
for (let i = 0; i < n; i++) {
table[i][0] = arr[i];
}
// Fill the sparse table using dynamic programming
for (let j = 1; j <= k; j++) {
for (let i = 0; i + (1 << j) <= n; i++) {
table[i][j] = Math.min(table[i][j - 1], table[i + (1 << (j - 1))][j - 1]);
}
}
return table;
}
// Example usage:
const arr = [1, 3, 2, 7, 9, 11];
const sparseTable = buildSparseTable(arr);
console.log(sparseTable);
Note: The sparse table uses the property that any range [L, R] can be covered by two overlapping ranges of size 2^j where j is the largest power such that 2^j ≤ (R - L + 1).
3. Implementing Range Minimum Query
| Operation | Description | Time Complexity | Space Complexity |
|---|---|---|---|
| Preprocessing | Build sparse table for range minimum queries | O(n log n) |
O(n log n) |
| Query | Find minimum in range [L, R] | O(1) |
O(1) |
Example: Sparse Table Implementation
class SparseTable {
constructor(arr) {
const n = arr.length;
const k = Math.floor(Math.log2(n)) + 1;
this.st = Array(n).fill().map(() => Array(k).fill(0));
this.log = Array(n + 1).fill(0);
for (let i = 2; i <= n; i++) {
this.log[i] = this.log[i / 2] + 1;
}
for (let i = 0; i < n; i++) {
this.st[i][0] = arr[i];
}
for (let j = 1; j < k; j++) {
for (let i = 0; i + (1 << j) <= n; i++) {
this.st[i][j] = Math.min(
this.st[i][j - 1],
this.st[i + (1 << (j - 1))][j - 1]
);
}
}
}
query(l, r) {
const j = this.log[r - l + 1];
return Math.min(this.st[l][j], this.st[r - (1 << j) + 1][j]);
}
}
// Example usage:
const arr = [1, 3, 2, 7, 9, 11];
const st = new SparseTable(arr);
console.log(st.query(1, 4)); // Output: 2
Note: The sparse table is built once and supports
O(1) range minimum queries after preprocessing.
4. Implementing Range Maximum Query
| Operation | Description | Time Complexity | Space Complexity |
|---|---|---|---|
| Preprocessing | Build sparse table for range maximum queries | O(n log n) |
O(n log n) |
| Query | Find maximum in range [L, R] | O(1) |
O(1) |
Example: Range Maximum Query Implementation
class SparseTable {
constructor(arr) {
const n = arr.length;
const k = Math.floor(Math.log2(n)) + 1;
this.st = Array(n).fill().map(() => Array(k).fill(0));
this.log = Array(n + 1).fill(0);
for (let i = 2; i <= n; i++) {
this.log[i] = this.log[i / 2] + 1;
}
for (let i = 0; i < n; i++) {
this.st[i][0] = arr[i];
}
for (let j = 1; j < k; j++) {
for (let i = 0; i + (1 << j) <= n; i++) {
this.st[i][j] = Math.max(
this.st[i][j - 1],
this.st[i + (1 << (j - 1))][j - 1]
);
}
}
}
query(l, r) {
const j = this.log[r - l + 1];
return Math.max(this.st[l][j], this.st[r - (1 << j) + 1][j]);
}
}
const arr = [1, 3, 2, 7, 9, 1];
const sparseTable = new SparseTable(arr);
console.log(sparseTable.query(1, 4)); // Output: 9
Note: The sparse table is built using dynamic programming where
st[i][j] stores the maximum value in the range [i, i + 2^j - 1].
5. Implementing Range GCD Query
| Operation | Description | Time Complexity | Space Complexity |
|---|---|---|---|
| Preprocessing | Build sparse table for GCD queries | O(n log n) |
O(n log n) |
| Query | Find GCD of elements in range [L, R] | O(1) |
O(1) |
Example: Range GCD Query Implementation
function buildSparseTable(arr) {
const n = arr.length;
const k = Math.floor(Math.log2(n)) + 1;
const table = Array(n).fill().map(() => Array(k).fill(0));
// Initialize base case (2^0 = 1)
for (let i = 0; i < n; i++) {
table[i][0] = arr[i];
}
// Build sparse table
for (let j = 1; j < k; j++) {
for (let i = 0; i + (1 << j) <= n; i++) {
table[i][j] = gcd(table[i][j - 1], table[i + (1 << (j - 1))][j - 1]);
}
}
return table;
}
function rangeGCD(table, L, R) {
const k = Math.floor(Math.log2(R - L + 1));
return gcd(table[L][k], table[R - (1 << k) + 1][k]);
}
function gcd(a, b) {
while (b !== 0) {
[a, b] = [b, a % b];
}
return a;
}
// Example usage
const arr = [2, 3, 6, 9, 12];
const sparseTable = buildSparseTable(arr);
console.log(rangeGCD(sparseTable, 1, 3)); // Output: 3
Note: The sparse table is built once and supports
O(1) range GCD queries.
6. Handling Non-Overlapping Ranges
| Operation | Description | Time Complexity | Space Complexity |
|---|---|---|---|
| Query Range | Retrieve the result for a specific range [L, R] | O(1) |
O(n log n) |
| Update Value | Modify a single element in the array | O(log n) |
O(1) |
Example: Query Non-Overlapping Ranges
const sparseTable = new SparseTable([1, 3, 2, 5, 4]);
console.log(sparseTable.query(1, 3)); // Output: 2 (min of [3, 2, 5])
console.log(sparseTable.query(0, 4)); // Output: 1 (min of [1, 3, 2, 5, 4])
Note: For non-overlapping ranges, the sparse table supports efficient range queries but updates are more expensive due to rebuilding affected segments.
7. Calculating Query in Constant Time
| Operation | Description | Time Complexity | Space Complexity |
|---|---|---|---|
| Query Range | Find minimum/maximum in a range [L, R] | O(1) |
O(n log n) |
Example: Range Minimum Query (RMQ)
const preprocess = (arr) => {
const n = arr.length;
const k = Math.floor(Math.log2(n)) + 1;
const sparseTable = Array(n).fill().map(() => Array(k).fill(0));
// Initialize base case (2^0 = 1)
for (let i = 0; i < n; i++) {
sparseTable[i][0] = arr[i];
}
// Build sparse table
for (let j = 1; (1 << j) <= n; j++) {
for (let i = 0; i + (1 << j) - 1 < n; i++) {
sparseTable[i][j] = Math.min(
sparseTable[i][j - 1],
sparseTable[i + (1 << (j - 1))][j - 1]
);
}
}
return sparseTable;
};
const query = (sparseTable, L, R) => {
const j = Math.floor(Math.log2(R - L + 1));
return Math.min(
sparseTable[L][j],
sparseTable[R - (1 << j) + 1][j]
);
};
// Example usage:
const arr = [1, 3, 2, 7, 9, 11];
const sparseTable = preprocess(arr);
console.log(query(sparseTable, 1, 4)); // Output: 2
8. Preprocessing Table
| Operation | Description | Time Complexity | Space Complexity |
|---|---|---|---|
| Build Sparse Table | Precompute all range queries for a given array using dynamic programming approach. | O(n log n) |
O(n log n) |
| Query Range Minimum | Find minimum element in a given range using precomputed values. | O(1) |
|
| Query Range Sum | Compute sum of elements in a given range using sparse table. | O(1) |
Example: Building Sparse Table for Range Minimum Query
function buildSparseTable(arr) {
const n = arr.length;
const k = Math.floor(Math.log2(n));
const table = Array(n).fill(0).map(() => Array(k + 1).fill(0));
// Initialize base case (2^0 = 1 intervals)
for (let i = 0; i < n; i++) {
table[i][0] = arr[i];
}
// Fill the sparse table using dynamic programming
for (let j = 1; j <= k; j++) {
for (let i = 0; i + (1 << j) <= n; i++) {
table[i][j] = Math.min(table[i][j - 1], table[i + (1 << (j - 1))][j - 1]);
}
}
return table;
}
// Example usage:
const arr = [1, 3, 2, 7, 9, 1];
const sparseTable = buildSparseTable(arr);
console.log(sparseTable);
Note: The sparse table is built using the formula
table[i][j] = min(table[i][j-1], table[i + 2^(j-1)][j-1]) where j represents the power of 2 for interval size.
Preprocessing Steps
- Initialize a 2D array
tableof sizen × log₂(n). - Set base case:
table[i][0] = arr[i]. - Iteratively compute values using the recurrence relation.
- Each query can be answered in
O(1)time after preprocessing.
9. Solving Range Bitwise OR
| Operation | Description | Time Complexity | Space Complexity |
|---|---|---|---|
| Preprocessing | Build sparse table for bitwise OR queries | O(n log n) | O(n log n) |
| Query | Range bitwise OR from index l to r | O(1) | O(1) |
Example: Range Bitwise OR Query
const arr = [1, 3, 5, 7, 9];
const n = arr.length;
const k = Math.floor(Math.log2(n));
const sparseTable = Array(n).fill(0).map(() => Array(k + 1).fill(0));
// Preprocessing
for (let i = 0; i < n; i++) {
sparseTable[i][0] = arr[i];
}
for (let j = 1; (1 << j) <= n; j++) {
for (let i = 0; i + (1 << j) - 1 < n; i++) {
sparseTable[i][j] = sparseTable[i][j - 1] | sparseTable[i + (1 << (j - 1))][j - 1];
}
}
// Query: OR from index 1 to 3
const l = 1, r = 3;
let result = 0;
for (let j = k; j >= 0; j--) {
if ((1 << j) <= r - l + 1) {
result |= sparseTable[l][j];
l += (1 << j);
}
}
console.log(result); // 7 (3 | 5 | 7)
Note: The sparse table is built using the OR operation, and queries are answered in O(1) time after O(n log n) preprocessing.
10. Solving Range Bitwise AND
The Sparse Table pattern is a powerful technique for answering range queries efficiently, particularly when the operation is idempotent (e.g., min, max, GCD, bitwise AND). For range bitwise AND queries, the Sparse Table can be preprocessed to allow O(1) query time after O(n log n) preprocessing.
| Operation | Description | Time Complexity | Space Complexity |
|---|---|---|---|
| Preprocessing | Build a sparse table where st[i][j] stores the bitwise AND of elements from index i to i + 2^j - 1 |
O(n log n) | O(n log n) |
| Query | For range [l, r], find the bitwise AND of all elements in that range |
O(1) | - |
Example: Range Bitwise AND Query
function buildSparseTable(arr) {
const n = arr.length;
const k = Math.floor(Math.log2(n));
const st = Array(n).fill(0).map(() => Array(k + 1).fill(-1));
// Initialize with original array
for (let i = 0; i < n; i++) {
st[i][0] = arr[i];
}
// Build sparse table
for (let j = 1; j <= k; j++) {
for (let i = 0; i + (1 << j) <= n; i++) {
st[i][j] = st[i][j - 1] & st[i + (1 << (j - 1))][j - 1];
}
}
return st;
}
function rangeAnd(st, l, r) {
let result = st[l][0];
for (let j = Math.floor(Math.log2(r - l + 1)); j >= 0; j--) {
if ((1 << j) <= r - l + 1) {
result &= st[l][j];
l += (1 << j);
}
}
return result;
}
// Example usage:
const arr = [15, 7, 3, 1];
const sparseTable = buildSparseTable(arr);
console.log(rangeAnd(sparseTable, 0, 3)); // Output: 1
Note: The bitwise AND operation is not commutative, but it is associative and idempotent, which makes it compatible with the Sparse Table approach.
11. Implementing 2D Sparse Table
A 2D Sparse Table is a data structure that allows efficient range queries on a 2D grid, similar to the 1D version but extended to two dimensions. It is particularly useful for problems involving range minimum/maximum queries or other associative operations over rectangular subgrids.
| Operation | Description | Time Complexity | Space Complexity |
|---|---|---|---|
| Preprocessing | Builds the sparse table for 2D queries | O(m * n * log m * log n) |
O(m * n * log m * log n) |
| Query | Range query over a rectangular subgrid | O(1) |
- |
Example: 2D Sparse Table for Range Maximum Query
class SparseTable2D {
constructor(matrix) {
const m = matrix.length;
const n = matrix[0].length;
this.m = m;
this.n = n;
const logM = Math.floor(Math.log2(m)) + 1;
const logN = Math.floor(Math.log2(n)) + 1;
this.st = Array(logM).fill().map(() =>
Array(logN).fill().map(() =>
Array(m).fill().map(() =>
Array(n).fill(-Infinity)
)
)
);
// Initialize base table (2^0 x 2^0)
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
this.st[0][0][i][j] = matrix[i][j];
}
}
// Build sparse table
for (let i = 0; i < logM; i++) {
for (let j = 0; j < logN; j++) {
if (i === 0 && j === 0) continue;
const halfI = 1 << i;
const halfJ = 1 << j;
for (let x = 0; x + halfI <= m; x++) {
for (let y = 0; y + halfJ <= n; y++) {
if (i === 0) {
this.st[i][j][x][y] = Math.max(
this.st[i][j-1][x][y],
this.st[i][j-1][x][y + halfJ / 2]
);
} else if (j === 0) {
this.st[i][j][x][y] = Math.max(
this.st[i-1][j][x][y],
this.st[i-1][j][x + halfI / 2][y]
);
} else {
this.st[i][j][x][y] = Math.max(
this.st[i-1][j-1][x][y],
this.st[i-1][j-1][x][y + halfJ / 2],
this.st[i-1][j-1][x + halfI / 2][y],
this.st[i-1][j-1][x + halfI / 2][y + halfJ / 2]
);
}
}
}
}
}
}
query(x1, y1, x2, y2) {
const k1 = Math.floor(Math.log2(x2 - x1 + 1));
const k2 = Math.floor(Math.log2(y2 - y1 + 1));
const halfI = 1 << k1;
const halfJ = 1 << k2;
return Math.max(
this.st[k1][k2][x1][y1],
this.st[k1][k2][x1][y2 - halfJ + 1],
this.st[k1][k2][x2 - halfI + 1][y1],
this.st[k1][k2][x2 - halfI + 1][y2 - halfJ + 1]
);
}
}
// Example usage:
const matrix = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
];
const sparseTable = new SparseTable2D(matrix);
console.log(sparseTable.query(0, 0, 1, 1)); // Output: 5
Note: The 2D sparse table is built using a similar principle to the 1D version, but extended to two dimensions. The preprocessing step is more expensive due to the additional dimension, but queries are still O(1).