Sparse Table

Introduction: The “Zero Latency” Search

Imagine you have a fixed dataset, like historical weather records. You need to answer thousands of queries like: “What was the lowest temperature between Day X and Day Y?”

If the data never changes, why settle for $O(\log N)$ (Segment Tree)? Sparse Table uses dynamic programming to precalculate overlapping ranges, allowing it to answer any Range Minimum Query (RMQ) in constant time $O(1)$.

What Problem does it solve?

• Input: A static array (no updates allowed).
• Output: The minimum or maximum element in any arbitrary range [L, R].
• The Promise: Fastest possible query time ($O(1)$).

Core Idea (Intuition)

The logic is “Doubling”:

1. Precalculate the minimum for all ranges of length 1, 2, 4, 8, … (powers of 2).
2. Store these in a table st[i][j] meaning: “Min value starting at index i with length $2^j$.”
3. The Overlap Magic: Any range [L, R] can be covered by two overlapping ranges of a power-of-2 length. For example, a range of length 7 can be covered by two overlapping ranges of length 4.
4. Since min(A, B) is the same even if A and B overlap, we just take the minimum of these two precalculated values.

How it Works

1. Preprocessing: Use DP: st[i][j] = min(st[i][j-1], st[i + 2^{j-1}][j-1]). This takes $O(N \log N)$.
2. Query:
   • Calculate $k = \lfloor \log_2(R - L + 1) floor$.
   • Result = min(st[L][k], st[R - 2^k + 1][k]).

Typical Business Scenarios

• ✅ Historical Analytics: Querying minimum/maximum values in fixed time series (e.g., “Max CPU load in 2023”).

• ✅ LCA (Lowest Common Ancestor): The standard way to find LCA in trees involves turning the tree into an array and performing an RMQ using a Sparse Table.

• ✅ String Algorithms: Finding the Longest Common Prefix (LCP) between two substrings.

• ❌ Dynamic Data: If even one element in your array changes, you have to re-run the entire $O(N \log N)$ preprocessing. Use a Segment Tree instead for dynamic data.

Performance & Complexity

• Query: $O(1)$.
• Preprocessing: $O(N \log N)$.
• Space: $O(N \log N)$ to store the table.

Summary

“Sparse Table is the ‘Speed Demon’ for static data. By precalculating powers-of-2 ranges, it exploits the overlap property to answer min/max queries in a single step.”