Pattern Guide
Sparse Table & Binary Lifting
"Precompute powers of 2. Answer range min/max in O(1)."
Sparse Table answers range minimum/maximum queries in O(1) after O(n log n) preprocessing. Binary lifting on trees answers LCA (Lowest Common Ancestor) queries in O(log n). Both use the same "jumping by powers of 2" trick. Use these when you have many queries on a static array/tree.
18 min readadvanced tree problems →
Problems you can solve with this pattern
4 problems · click any to start solving
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 insteadSparse 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)
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)];
}
}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