Sparse Table (Range Minimum Query)

Sparse tables are the static-range-query end of the spectrum: spend $O(n\log n)$ upfront, answer idempotent range queries in $O(1)$, and accept that updates are off the table.

Difficulty: Intermediate | Prerequisites: Segment Tree

---

Intuition

The problem: a fixed array, no updates, and a flood of range-minimum queries. Scanning each range naively works once; it falls apart fast.

a[] = { 3, 1, 4, 1, 5, 9, 2, 6 }

Five queries against this array, scanning every element each time:

query(0, 7):  scan 8 elements  ->  min = 1    (8 ops)
query(2, 5):  scan 4 elements  ->  min = 1    (4 ops)
query(4, 7):  scan 4 elements  ->  min = 2    (4 ops)
query(1, 3):  scan 3 elements  ->  min = 1    (3 ops)
query(0, 2):  scan 3 elements  ->  min = 1    (3 ops)
                                         total: 22 ops

Each query still costs $O(n)$. With $q={10}^6$ queries on $n={10}^6$ elements, that's ${10}^{12}$ operations—far too slow. The fix is to push the work into preprocessing so each query costs nothing at runtime.

Precompute the minimum for every power-of-2 length range, then answer any query by overlapping two precomputed ranges whose union covers $[l,r]$.

Because $min$ is idempotent—$min(x,x)=x$—the overlap does not corrupt the answer. Elements counted twice still contribute the same minimum they contributed once.

Analogy: Imagine a chain of security cameras, each covering a power-of-2 stretch of hallway. To monitor any segment, you activate the two largest cameras whose views span it. Their overlap is harmless—you just see the same stretch twice, and the "most suspicious activity" (minimum) stays the same.

Preprocessing: $O(n\log n)$—fill in one row of the table per power of 2. Query: $O(1)$—look up two precomputed values and take their $min$.

Visual Walkthrough

Array: a[] = { 3, 1, 4, 1, 5, 9, 2, 6 } with $n=8$.

Step 1—Row $k=0$ (windows of length $2^0=1$): copy the array.

i:        0   1   2   3   4   5   6   7
sp[0]:  [ 3 | 1 | 4 | 1 | 5 | 9 | 2 | 6 ]
          ^   ^   ^   ^   ^   ^   ^   ^
          each cell is min of 1 element = itself

Operations: 0 comparisons (just copy). Running total: 0.

Step 2—Row $k=1$ (windows of length $2^1=2$): merge adjacent pairs.

sp[1][i] = min(sp[0][i], sp[0][i+1])

i:        0   1   2   3   4   5   6
sp[1]:  [ 1 | 1 | 1 | 1 | 5 | 2 | 2 ]
          |       |       |       |
          min(3,1)min(4,1)min(5,9)min(2,6)

Operations: 7 comparisons. Running total: 7.

Step 3—Row $k=2$ (windows of length $2^2=4$): merge pairs from row 1.

sp[2][i] = min(sp[1][i], sp[1][i+2])

i:        0   1   2   3   4
sp[2]:  [ 1 | 1 | 1 | 1 | 2 ]
          |           |
          min(sp[1][0], sp[1][2])  = min(1,1) = 1
                      min(sp[1][3], sp[1][5]) = min(1,2) = 1

Operations: 5 comparisons. Running total: 12.

Step 4—Row $k=3$ (windows of length $2^3=8$): merge pairs from row 2.

sp[3][i] = min(sp[2][i], sp[2][i+4])

i:        0
sp[3]:  [ 1 ]
          min(sp[2][0], sp[2][4]) = min(1,2) = 1

Operations: 1 comparison. Running total: 13.

Build complete: 13 comparisons for $n=8$, which is the expected $O(n\log n)$ preprocessing cost.

Answering query(2, 7):

Length = 7 - 2 + 1 = 6
k = floor(log2(6)) = 2       (so 2^k = 4)

Interval A: sp[2][2] = min(a[2..5]) = 1
                  |<-- 2^2=4 -->|
Index:  0   1   2   3   4   5   6   7
              [ 4   1   5   9 ]

Interval B: sp[2][7-4+1] = sp[2][4] = min(a[4..7]) = 2
                          |<-- 2^2=4 -->|
Index:  0   1   2   3   4   5   6   7
                      [ 5   9   2   6 ]

              +---+---+---+---+
    A:        | 4 | 1 | 5 | 9 |
              +---+---+---+---+
                      +---+---+---+---+
    B:                | 5 | 9 | 2 | 6 |
                      +---+---+---+---+
                  overlap ^^^

Answer = min(1, 2) = 1       (2 lookups + 1 comparison = O(1))

The naive query(2, 7) costs 6 comparisons; the sparse table costs 1—after a one-time build. Over many queries, preprocessing more than pays for itself, and every subsequent query stays constant time.

The Invariant

+------------------------------------------------------------------+
|  sp[k][i] = min of a[i .. i + 2^k - 1]                          |
|                                                                  |
|  For any range [l, r], let k = floor(log2(r - l + 1)).          |
|  Then [l, r] is fully covered by the union of:                   |
|      [l,  l + 2^k - 1]    and    [r - 2^k + 1,  r]             |
|  These two sub-ranges overlap, and because min is idempotent,    |
|  answer = min(sp[k][l], sp[k][r - 2^k + 1]).                    |
+------------------------------------------------------------------+

Connection to walkthrough: In Step 3 we stored $\text{sp}[2][2]=1$ for $a[2..5]$ and $\text{sp}[2][4]=2$ for $a[4..7]$. The query picked exactly those two cells because $k=2$ was the largest power that fits inside a length-6 window, and their union $[2..5]\cup [4..7]=[2..7]$ covers the query range. The overlap at indices 4–5 is harmless.

Why Idempotency Is the Gatekeeper

Building the table is straightforward DP. The clever part is the query: two power-of-2 windows whose union covers $[l,r]$, even though they overlap. That only works because the answer is immune to seeing the same element twice—idempotency is doing the real work.

  query(2, 9), k = 3, 2^k = 8

  Index:  0   1   2   3   4   5   6   7   8   9
              |-------------------------------|  query range [2,9]

  A = sp[3][2]:  covers [2 ................. 9]
                 |---------------------------|

  B = sp[3][2]:  covers [2 ................. 9]
                 |---------------------------|

  (When 2^k exactly fits, A = B -- that's fine, just a redundant lookup.)

  query(2, 7), k = 2, 2^k = 4

  Index:  0   1   2   3   4   5   6   7
              |-----------------------|  query range [2,7]

  A = sp[2][2]:  |-----------|              covers [2,5]
  B = sp[2][4]:          |-----------|      covers [4,7]
                         |---|              overlap [4,5]

  answer = min(A, B)
  Overlap is harmless: min(x, x) = x  -- OK

Sparse table sits at the extreme of the precompute-vs-query spectrum. You burn $O(n\log n)$ at build time so that queries cost nothing. That trade only makes sense when queries vastly outnumber builds—which is exactly the competitive programming setting, but not an online system with updates.

The overlap trick requires $f(x,x)=x$. If your operation is not idempotent, overlapping elements corrupt the answer—there is no workaround within the sparse-table framework. Use prefix sums for sums, or a segment tree for XOR and products.

  Idempotent ops (overlap-safe):       Non-idempotent ops (overlap-breaks):
  +------------------------------+     +------------------------------+
  |  min(x, x) = x          [Y]  |     |  x + x = 2x   != x      [N]  |
  |  max(x, x) = x          [Y]  |     |  x ^ x = 0    != x      [N]  |
  |  gcd(x, x) = x          [Y]  |     |  x * x = x^2  != x      [N]  |
  |  x AND x   = x          [Y]  |     |                              |
  |  x OR  x   = x          [Y]  |     |                              |
  +------------------------------+     +------------------------------+

One last code-level trap: use integer log, never floating-point log2(). (int)log2(8) can return 2 instead of 3 due to floating-point rounding, silently giving wrong answers on specific inputs. Always use __lg() (GCC) or precompute a log table.

When to Reach for This

These phrases in a problem statement are your green light:

• "static array" + "range minimum / maximum / GCD"
• "no updates", "array does not change"
• "$O(1)$ per query" or very tight time limits with $\ge {10}^6$ queries
• "LCA on a tree" (reduce to RMQ on Euler tour)
• "idempotent" operation on static ranges

When not to use sparse table:

Situation	Use instead
Array has point or range updates	Segment tree
Operation is sum (non-idempotent)	Prefix sums
Operation is xor / product	Segment tree or disjoint sparse table
$n>2\times {10}^6$ and memory is tight	Segment tree ($O(4n)$ memory)
Need online build (elements arrive one by one)	Segment tree

---

C++ STL Reference

Function / Builtin	Header	Description	Notes
__lg(x)	(GCC builtin)	$\lfloor {\log }_{2}x\rfloor$ for $x>0$	Fastest; works on int/long long
__builtin_clz(x)	(GCC builtin)	Count leading zeros of unsigned $x$	$\lfloor {\log }_{2}x\rfloor =31-\text{\_\_builtin\_clz}(x)$
__builtin_clzll(x)	(GCC builtin)	Same for unsigned long long	$63-\text{\_\_builtin\_clzll}(x)$
std::log2(x)	<cmath>	Floating-point ${\log }_2$	Avoid in inner loops (slow, rounding issues)
std::min(a, b)	<algorithm>	Minimum of two values	Use for RMQ merge
std::gcd(a, b)	<numeric>	GCD (C++17)	Use for range-GCD sparse table
std::array	<array>	Fixed-size array	Good for compile-time $K$ bound

---

Implementation

Minimal Contest Template

#include <bits/stdc++.h>
using namespace std;

// Sparse Table for Range Minimum Query (0-indexed)
struct SparseTable {
    int n;
    vector<vector<int>> sp;

    SparseTable() = default;

    SparseTable(const vector<int>& a) : n((int)a.size()) {
        int K = __lg(n) + 1;
        sp.assign(K, vector<int>(n));
        sp[0] = a;
        for (int k = 1; k < K; k++)
            for (int i = 0; i + (1 << k) <= n; i++)
                sp[k][i] = min(sp[k - 1][i], sp[k - 1][i + (1 << (k - 1))]);
    }

    int query(int l, int r) const { // [l, r] inclusive
        int k = __lg(r - l + 1);
        return min(sp[k][l], sp[k][r - (1 << k) + 1]);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (auto& x : a) cin >> x;

    SparseTable st(a);
    while (q--) {
        int l, r;
        cin >> l >> r;
        cout << st.query(l, r) << '\n';
    }
}

Generic Operation—Explained

#include <bits/stdc++.h>
using namespace std;

// Generic Sparse Table for any idempotent operation.
// Op must satisfy: op(op(a, b), b) == op(a, b)  (idempotent)
// Examples: min, max, gcd, bitwise AND, bitwise OR
template <typename T, typename Op>
struct SparseTable {
    int n;
    vector<vector<T>> sp;
    Op op;

    // Build: O(n log n) time and space.
    // a: 0-indexed input array.
    SparseTable(const vector<T>& a, Op op) : n((int)a.size()), op(op) {
        int K = (n > 1) ? __lg(n) + 1 : 1;
        sp.assign(K, vector<T>(n));
        sp[0] = a;
        for (int k = 1; k < K; k++) {
            // sp[k][i] = op over a[i .. i + 2^k - 1]
            // Split into two halves of length 2^(k-1):
            //   a[i .. i+2^(k-1)-1]  and  a[i+2^(k-1) .. i+2^k-1]
            for (int i = 0; i + (1 << k) <= n; i++) {
                sp[k][i] = op(sp[k - 1][i], sp[k - 1][i + (1 << (k - 1))]);
            }
        }
    }

    // Query [l, r] inclusive, 0-indexed.
    // O(1) time: pick the largest k with 2^k <= r-l+1,
    // answer = op(sp[k][l], sp[k][r - 2^k + 1]).
    // The two intervals overlap, which is fine for idempotent ops.
    T query(int l, int r) const {
        int k = __lg(r - l + 1);
        return op(sp[k][l], sp[k][r - (1 << k) + 1]);
    }
};

// CTAD deduction guide: lets you write SparseTable(vec, lambda)
// without spelling out template parameters.
template <typename T, typename Op>
SparseTable(const vector<T>&, Op) -> SparseTable<T, Op>;

// --- Usage examples ---

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    vector<int> a = {3, 1, 4, 1, 5, 9, 2, 6};

    // RMQ (range minimum) -- CTAD deduces SparseTable<int, lambda>
    auto rmq = SparseTable(a, [](int a, int b){ return min(a, b); });
    cout << rmq.query(2, 7) << '\n'; // 1

    // Range maximum
    auto rmax = SparseTable(a, [](int a, int b){ return max(a, b); });
    cout << rmax.query(0, 3) << '\n'; // 4

    // Range GCD
    vector<int> b = {12, 18, 24, 36};
    auto rgcd = SparseTable(b, [](int a, int b){ return gcd(a, b); });
    cout << rgcd.query(0, 3) << '\n'; // 6
}

---

Operations Reference

The build/query cost split is the defining feature—all work happens upfront so queries are free.

Operation	Time	Space	Notes
Build	$O(n\log n)$	$O(n\log n)$	One-time precomputation
Query (idempotent)	$O(1)$	--	$min,max,gcd,\text{AND},\text{OR}$
Query (non-idempotent)	N/A	--	Use prefix sums or segment tree
Point update	N/A	--	Not supported; rebuild is $O(n\log n)$
Memory (bytes)	--	$\approx 4n\lceil {\log }_{2}n\rceil$	For int values

Comparison at $n={10}^6$:

	Sparse Table	Segment Tree	Prefix Sums
Build	$\sim 20\times {10}^6$ ops	$\sim 4\times {10}^6$ ops	$\sim {10}^6$ ops
Query	$O(1)$	$O(\log n)$	$O(1)$
Update	rebuild	$O(\log n)$	rebuild
Ops supported	idempotent only	any associative	sum only

---

Problem Patterns

Static RMQ (Direct Application)

The textbook case: a fixed array, many range-min/max queries, no updates.

Approach: Build once in $O(n\log n)$, answer each query in $O(1)$.

SparseTable st(a);
cout << st.query(l, r);

Problems:

• CF 514D -- R2D2 and Droid Army
• CSES -- Static Range Minimum Queries

LCA via Sparse Table (Euler Tour + RMQ)

Reduce LCA to RMQ on the Euler tour. Build sparse table on depths. Query $\text{LCA}(u,v)$ in $O(1)$.

Euler tour of a tree:
      1
     / \
    2   3
   / \
  4   5

tour:   [1, 2, 4, 2, 5, 2, 1, 3, 1]
depth:  [0, 1, 2, 1, 2, 1, 0, 1, 0]
first:  first[1]=0, first[2]=1, first[3]=7,
        first[4]=2, first[5]=4

LCA(4,5) = node at min-depth in tour[first[4]..first[5]]
         = tour[3] = 2   (depth 1)

// After building Euler tour with (depth, node) pairs:
// SparseTable over (depth, node) with min on depth.
auto lca = [&](int u, int v) {
    int l = first[u], r = first[v];
    if (l > r) swap(l, r);
    return st.query(l, r).second; // .second is the node id
};

Problems:

• CF 191C -- Fools and Roads
• CF 609E -- Minimum spanning tree for each edge

Range GCD Queries

$gcd$ is idempotent—$gcd(x,x)=x$—so the overlap trick is safe and sparse table applies directly.

auto rgcd = SparseTable(a, [](int a, int b){ return gcd(a, b); });

Problems:

• CF 475D -- CGCDSSQ
• CF 1549D -- Integers Have Friends

Sliding Window Min/Max

For a fixed-length sliding window, both sparse table ($O(1)$ per query) and monotonic deque ($O(1)$ amortized) work. If you already have a sparse table built, use it—the query is a one-liner and there is nothing to maintain.

SparseTable st(a);
for (int i = 0; i + k - 1 < n; i++)
    cout << st.query(i, i + k - 1) << " \n"[i + k == n];

Problems:

• CF 1611F -- ATM and Students

Two Pointers + RMQ

Hold the left pointer fixed and advance the right pointer, using $O(1)$ RMQ to check a condition on the current window in constant time. This turns an $O(n^2)$ two-pointer check into $O(n)$.

Example: Find the longest subarray where $max-min\le k$.

SparseTable stMin(a), stMax(a); // min and max tables
int ans = 0;
for (int l = 0, r = 0; l < n; l++) {
    while (r < n && stMax.query(l, r) - stMin.query(l, r) <= k)
        r++;
    ans = max(ans, r - l);
}

Problems:

• CF 1555E -- Boring Segments

Binary Search + RMQ

Binary-search on the answer and verify the candidate with a sparse table query inside the check. $O(1)$ verification keeps the full binary search at $O(n\log n)$ total, faster than recomputing the range from scratch each time.

Problems:

• CF 1237D -- Balanced Playlist

---

Contest Cheat Sheet

+----------------------------------------------------------+
|  SPARSE TABLE -- QUICK REFERENCE                         |
+----------------------------------------------------------+
|  WHEN:  static array + range min/max/gcd/AND/OR          |
|         no updates needed                                |
|         need O(1) query (many queries, tight TL)         |
|                                                          |
|  BUILD:  int K = __lg(n) + 1;                            |
|          sp[0] = a;                                      |
|          for k in [1,K): for i with i+2^k <= n:          |
|            sp[k][i] = min(sp[k-1][i],                    |
|                          sp[k-1][i + (1<<(k-1))]);       |
|                                                          |
|  QUERY(l, r):                                            |
|          k = __lg(r - l + 1);                            |
|          return min(sp[k][l], sp[k][r-(1<<k)+1]);        |
|                                                          |
|  COMPLEXITY:  Build O(n log n) / Query O(1)              |
|  MEMORY:      O(n log n)  (~80 MB at n=10^7, int)       |
|                                                          |
|  DOES NOT WORK FOR: sum, xor, product (non-idempotent)   |
|  USE INSTEAD:  prefix sums (sum), seg tree (updates)     |
|                                                          |
|  IDEMPOTENT = f(x,x) = x                                |
|  min, max, gcd, AND, OR  -- all OK                       |
+----------------------------------------------------------+

---

Common Mistakes & Debugging

Non-Idempotent Operations Silently Give Wrong Answers

The overlap query double-counts elements in the overlapping region. For $min$ that is harmless; for $\text{sum}$ or $\text{xor}$ it silently corrupts every answer.

Fix: Use prefix sums for sum. Use a segment tree or disjoint sparse table for non-idempotent operations.

Off-by-One in __lg(0)

__lg(0) is undefined—GCC returns $-1$, and the query immediately goes wrong. It strikes when l == r: __lg(r - l + 1) = __lg(1) = 0, which is fine. The danger is empty ranges or index arithmetic that produces __lg(0).

Fix: Always ensure $l\le r$ before querying.

Table Dimensions Wrong

If you set K = __lg(n) instead of __lg(n) + 1, the table is one row short—and a query whose range length is exactly $n$ will read past the end. $2^K$ must be able to cover the full array.

Fix: int K = __lg(n) + 1; (or K = __lg(max(n, 1)) + 1; to handle $n=1$).

1-Indexed vs. 0-Indexed Confusion

Most Codeforces problems use 1-indexed input; the template above uses 0-indexed. Mixing the two shifts every range by one and produces plausible-looking but wrong answers.

Fix: Store the array 0-indexed internally and convert at I/O boundaries:

int l, r;
cin >> l >> r;
cout << st.query(l - 1, r - 1) << '\n';

Memory Limit with Large $n$

At $n={10}^7$, the table uses $\approx n\times 24\times 4$ bytes $=960$ MB for int—well over any typical memory limit. For $n>2\times {10}^6$, consider a block decomposition or a segment tree with $O(\log n)$ queries instead.

Building Sparse Table on Pairs / Structs

When using RMQ for LCA via the Euler tour, you store pair<int,int> (depth, node). The comparison must minimize on depth only. Using min on pairs compares lexicographically—that happens to be correct when depth is .first, but verify your pair ordering before relying on it.

Using log2() from <cmath>

Floating-point log2 can round just below an integer. log2(8) may return 2.9999..., so (int)log2(8) = 2 instead of 3—silently picking the wrong table row for power-of-2 lengths.

Fix: Always use __lg() instead.

---

Mental Traps

"O(1) query must be better than O(log n)"

$O(1)$ query time is seductive, but consider the full picture:

  Scenario: n = 500,000 elements, q = 1,000 queries, with occasional updates

  Sparse Table:   Build  O(n log n) ~ 10,000,000 ops
                  Query  O(1) * 1000 = 1,000 ops
                  Update: impossible -- must rebuild entirely
                  Total: ~10,001,000 + rebuild cost per update

  Segment Tree:   Build  O(n) ~ 2,000,000 ops
                  Query  O(log n) * 1000 ~ 19,000 ops
                  Update O(log n) per update -- no rebuild needed
                  Total: ~2,019,000 + cheap updates

Sparse table wins when $q\gg n$ and there are no updates. Otherwise, the $O(n\log n)$ build dominates, and a segment tree is both faster to build and more flexible. Think about total work, not just query complexity.

"Sparse table works for sum / xor"

The overlap trick requires idempotency. With sum, overlapping elements get counted twice—inflating the result. With XOR, they cancel each other out to zero. Both failures are silent: no crash, just wrong answers.

  a[] = { 3, 1, 4, 1, 5 }    query(0, 4), k = 2, 2^k = 4

  Index:    0     1     2     3     4
            |-----------------|            A covers [0,3]
                  |-----------------|      B covers [1,4]
                  |-----------|            overlap [1,2,3]

  +---------------------------------------------------------+
  |  IDEMPOTENT (min):                                      |
  |    A = min(3,1,4,1) = 1                                 |
  |    B = min(1,4,1,5) = 1                                 |
  |    result = min(1, 1) = 1     <- correct                |
  |    (overlap elements 1,4,1 counted twice, but min(x,x)  |
  |     = x, so no harm done)                               |
  |---------------------------------------------------------|
  |  NON-IDEMPOTENT (sum):                                  |
  |    A = 3+1+4+1 = 9                                      |
  |    B = 1+4+1+5 = 11                                     |
  |    result = 9 + 11 = 20       <- WRONG                  |
  |    actual = 3+1+4+1+5 = 14                              |
  |    (overlap elements 1,4,1 added twice: 6 extra)        |
  |---------------------------------------------------------|
  |  NON-IDEMPOTENT (xor):                                  |
  |    A = 3^1^4^1 = 7                                      |
  |    B = 1^4^1^5 = 1                                      |
  |    result = 7 ^ 1 = 6         <- WRONG                  |
  |    actual = 3^1^4^1^5 = 2                               |
  |    (overlap elements xor'd twice -> cancel to 0)        |
  +---------------------------------------------------------+

Rule of thumb: If $f(x,x)\ne x$, the overlap trick corrupts results. Use prefix sums for sum, segment tree for xor/product.

---

Self-Test

If you can answer all of these cold, you own the topic:

• [ ] Why does sparse table require the operation to be idempotent? What goes wrong with sum?
• [ ] Write the query formula from memory: given sp[][], l, r, how do you compute the answer in $O(1)$?
• [ ] Why is __lg() preferred over (int)log2() for computing $k$?
• [ ] What is the time and space complexity of building the table? Of a single query?
• [ ] When should you prefer a segment tree over a sparse table, even if no updates are needed?
• [ ] How do you reduce LCA queries to RMQ using an Euler tour?
• [ ] Explain the off-by-one: why is the second interval sp[k][r - (1<<k) + 1] and not sp[k][r - (1<<k)]?

---

Practice Problems

#	Problem	Source	Difficulty	Key Idea
1	Static Range Minimum Queries	CSES	Easy	Direct sparse table
2	CGCDSSQ	CF 475D	Medium	Range GCD + two pointers
3	R2D2 and Droid Army	CF 514D	Medium	RMQ + binary search / two pointers
4	Integers Have Friends	CF 1549D	Medium	Sparse table on differences + GCD
5	Minimum spanning tree for each edge	CF 609E	Medium	LCA via sparse table on MST
6	Fools and Roads	CF 191C	Medium	LCA + difference on tree
7	Boring Segments	CF 1555E	Hard	Sorting + sliding window + RMQ
8	Balanced Playlist	CF 1237D	Hard	Binary search + sparse table on doubled array

---

Further Reading

• cp-algorithms: Sparse Table—detailed explanation with Disjoint Sparse Table variant.
• CF Blog: Sparse Table (adamant)—advanced tricks and benchmarks.
• CF Blog: Range minimum query in O(1)—covers the Bender–Farach-Colton $O(n)$ build RMQ.
• Disjoint Sparse Table—handles non-idempotent associative operations in $O(1)$ query, $O(n\log n)$ build.
• Cartesian Tree—closely related; can reduce RMQ to LCA and vice versa.
• Segment Tree—more general; supports updates.
• Binary Indexed Tree (Fenwick)—supports prefix sum queries + point updates.
• Monotonic Queue / Deque—alternative for sliding-window min/max.
• Data Structure Selection Guide—when to pick sparse table vs. segment tree vs. BIT.
• Practice Ladder: Data Structures—graded problem set.