Pattern Reference
Sparse Table
"O(1) range min/max/gcd queries with O(n log n) preprocessing."
Loading...
Deep Dive Tutorial
Sparse table and binary lifting both exploit the same insight: any range [l, r] can be covered by two overlapping ranges of length 2^k (the largest power of 2 that fits). For idempotent operations (min, max, GCD), two overlapping answers can be combined. For sum, they can't — use Fenwick/Segment tree instead.
| Structure | Build | Query | Update | Use for |
|---|---|---|---|---|
| Prefix Sum | O(n) | O(1) | O(n) | Range sum (static) |
| Sparse Table | O(n log n) | O(1) | Not supported | Range min/max/GCD (static, idempotent ops) |
| Fenwick Tree | O(n log n) | O(log n) | O(log n) | Range sum with point updates |
| Segment Tree | O(n) | O(log n) | O(log n) | Any associative op with updates |
| Binary Lifting | O(n log n) | O(log n) | N/A | LCA queries on trees |
Sparse Table — O(1) Range Min/Max
Sparse Table — build O(n log n), query O(1)
class SparseTable {
constructor(arr) {
const n = arr.length;
const LOG = Math.floor(Math.log2(n)) + 1;
// st[k][i] = min of arr[i..i+2^k-1]
this.st = Array.from({length:LOG}, () => new Array(n).fill(0));
this.log = new Array(n + 1).fill(0);
for (let i = 2; i <= n; i++) this.log[i] = this.log[i>>1] + 1;
this.st[0] = [...arr]; // base: 2^0 = single elements
for (let k = 1; k < LOG; k++)
for (let i = 0; i + (1<<k) <= n; i++)
this.st[k][i] = Math.min(this.st[k-1][i], this.st[k-1][i + (1<<(k-1))]);
}
// Range min query [l, r] inclusive — O(1)
query(l, r) {
const k = this.log[r - l + 1];
return Math.min(this.st[k][l], this.st[k][r - (1<<k) + 1]);
// Two overlapping blocks of length 2^k covering [l,r]
// Works for min/max/GCD (idempotent — overlap is fine)
}
}
// NOTE: Does NOT work for sum/product (overlapping double-counts!)
// For sum: use Fenwick Tree or Prefix Sum insteadBinary Lifting — LCA in O(log n)
lightbulb
Lowest Common Ancestor (LCA): The deepest node that is an ancestor of both u and v.
Binary lifting approach:
1. Precompute up[k][v] = 2^k-th ancestor of node v (O(n log n))
2. For LCA(u,v): bring both nodes to the same depth, then jump together until they meet
3. Each LCA query: O(log n)
up[0][v] = parent[v]. up[k][v] = up[k-1][up[k-1][v]] (apply 2^(k-1) jump twice).
Binary lifting approach:
1. Precompute up[k][v] = 2^k-th ancestor of node v (O(n log n))
2. For LCA(u,v): bring both nodes to the same depth, then jump together until they meet
3. Each LCA query: O(log n)
up[0][v] = parent[v]. up[k][v] = up[k-1][up[k-1][v]] (apply 2^(k-1) jump twice).
Binary Lifting for LCA — O(n log n) preprocessing, O(log n) per query
class LCA {
constructor(n, adj, root = 0) {
this.LOG = Math.ceil(Math.log2(n + 1)) + 1;
this.depth = new Array(n).fill(0);
this.up = Array.from({length:this.LOG}, () => new Array(n).fill(-1));
// BFS/DFS to set parent and depth
const visited = new Array(n).fill(false);
const queue = [root];
visited[root] = true;
this.up[0][root] = root; // root's parent is itself
while (queue.length) {
const u = queue.shift();
for (const v of adj[u]) {
if (!visited[v]) {
visited[v] = true;
this.depth[v] = this.depth[u] + 1;
this.up[0][v] = u; // direct parent
queue.push(v);
}
}
}
// Build sparse table: up[k][v] = 2^k-th ancestor
for (let k = 1; k < this.LOG; k++)
for (let v = 0; v < n; v++)
this.up[k][v] = this.up[k-1][this.up[k-1][v]];
}
lca(u, v) {
// Bring to same depth
if (this.depth[u] < this.depth[v]) [u, v] = [v, u];
let diff = this.depth[u] - this.depth[v];
for (let k = 0; diff; k++, diff >>= 1)
if (diff & 1) u = this.up[k][u];
if (u === v) return u;
// Jump both up until they differ
for (let k = this.LOG - 1; k >= 0; k--)
if (this.up[k][u] !== this.up[k][v]) {
u = this.up[k][u]; v = this.up[k][v];
}
return this.up[0][u];
}
// Distance between two nodes
dist(u, v) {
return this.depth[u] + this.depth[v] - 2 * this.depth[this.lca(u, v)];
}
}Worked Problems
brain
When to use Sparse Table vs Segment Tree:
- Static array, many range min/max/GCD queries → Sparse Table (O(1) query)
- Array changes (point updates) → Fenwick or Segment Tree
- Range updates → Segment Tree with lazy propagation
- Tree LCA queries → Binary Lifting
Idempotent operations (can use sparse table): min, max, GCD, bitwise AND/OR
NOT idempotent (cannot use sparse table): sum, count, product — use prefix sums or Fenwick
- Static array, many range min/max/GCD queries → Sparse Table (O(1) query)
- Array changes (point updates) → Fenwick or Segment Tree
- Range updates → Segment Tree with lazy propagation
- Tree LCA queries → Binary Lifting
Idempotent operations (can use sparse table): min, max, GCD, bitwise AND/OR
NOT idempotent (cannot use sparse table): sum, count, product — use prefix sums or Fenwick