{"title":"Chapter 4: Sparse Table","description":"","content":"# Chapter 4: Sparse Table\n\nYou need to answer range minimum queries on a static array. Thousands of them, maybe millions. A naive loop over each range costs O(n) per query, and with 10^6 queries on an array of size 10^5, that is 10^11 operations. Far too slow. A segment tree brings it down to O(log n) per query, which works, but what if you could answer every query in O(1) after a one-time preprocessing step?\n\nThat is exactly what a Sparse Table does. It preprocesses a static array in O(n log n) time and space, then answers range minimum (or maximum, or GCD) queries in constant time. The catch: the array cannot change. No updates allowed. But when your data is immutable, which happens more often than you might think, a Sparse Table is the fastest range query structure there is.\n\n---\n\n## Why Sparse Table Matters\n\nSparse Tables occupy a specific but important niche in the algorithmic toolkit. Here is why they are worth learning:\n\n- **The fastest possible range minimum queries.** No other data structure achieves O(1) query time for range min/max with only O(n log n) preprocessing. If you need speed and your data does not change, nothing beats a Sparse Table.\n- **Competitive programming staple.** Problems involving static RMQ (Range Minimum Query) appear frequently in contests. Sparse Tables are the standard approach when the array is not modified after construction.\n- **Foundation for LCA algorithms.** The classic reduction of Lowest Common Ancestor to Range Minimum Query (the Euler tour technique) relies on Sparse Tables for O(1) LCA queries after O(n log n) preprocessing.\n- **Real-world applications.** Sparse Tables are used in text indexing (suffix arrays with LCP arrays), computational geometry (nearest point queries on preprocessed data), and bioinformatics (range queries over genomic data).\n- **Teaches a powerful technique.** The idea of precomputing answers for all power-of-2 length intervals and combining overlapping intervals is a technique that shows up in other contexts too, like binary lifting for LCA and jump pointers in linked lists.\n\n**Interview Insight:** Sparse Table questions are less common than segment tree questions in interviews, but they test something specific: whether you understand the difference between idempotent and non-idempotent operations, and whether you can reason about when overlapping intervals produce correct results. If an interviewer asks \"can you do better than O(log n) per query for static range minimum?\", knowing the Sparse Table answer sets you apart.\n\n---\n\n## The Core Idea\n\n### The Problem\n\nConsider the simplest approach to answering range minimum queries: for each query (l, r), iterate from index l to r and track the minimum. That is O(r - l + 1) per query, which is O(n) in the worst case. With many queries, this adds up fast.\n\nA segment tree improves this to O(log n) per query, which is excellent for dynamic data. But if the array never changes, we are paying for update capabilities we do not need. Can we trade away update support for even faster queries?\n\nYes. The Sparse Table does exactly that.\n\n### The Key Insight\n\nThe core observation behind Sparse Tables is that any range of length L can be covered by at most two overlapping ranges whose lengths are powers of 2.\n\nHere is why: for any range [l, r] of length L = r - l + 1, compute k = floor(log2(L)). The value 2^k is at least L/2. So the range [l, l + 2^k - 1] covers the first chunk, and the range [r - 2^k + 1, r] covers the last chunk. These two ranges overlap in the middle, but together they cover the entire [l, r] range.\n\nNow here is the key: if the operation you care about is **idempotent** (applying it to the same element twice does not change the result), then overlapping is perfectly fine. The minimum of a set does not change if you include some elements twice. Same for maximum, GCD, bitwise AND, and bitwise OR. For these operations, you can just combine the answers from two overlapping power-of-2 ranges, and the result is correct.\n\nSo the plan is simple: precompute the answer for every possible power-of-2 range in the array, then answer any query by combining two such ranges.\n\n### The Analogy\n\nThink of it like covering a hallway with two overlapping rugs. You have rugs in sizes 1, 2, 4, 8, 16 meters, and so on (powers of 2). No matter how long the hallway is, you can always pick a rug size that is at least half the hallway length, place one rug starting from the left end and another ending at the right end, and the two rugs together cover the entire hallway. Some floor in the middle gets covered twice, but if all you care about is \"is every spot covered?\" (an idempotent question), the overlap does not matter.\n\n### Visual Overview\n\nThe following diagram illustrates how a query range [2, 7] on an 8-element array is covered by two overlapping power-of-2 ranges of length 4.\n\n\n```mermaid\nflowchart TD\n subgraph Array[\"Array indices 0 through 7\"]\n direction LR\n A0[\"[0]\"]:::primary\n A1[\"[1]\"]:::primary\n A2[\"[2]\"]:::orange\n A3[\"[3]\"]:::orange\n A4[\"[4]\"]:::green\n A5[\"[5]\"]:::green\n A6[\"[6]\"]:::orange\n A7[\"[7]\"]:::orange\n end\n\n subgraph Ranges[\"Two overlapping ranges cover [2,7]\"]\n R1[\"Range 1: [2, 5]
length 2^2 = 4\"]:::orange\n R2[\"Range 2: [4, 7]
length 2^2 = 4\"]:::orange\n OV[\"Overlap: [4, 5]
OK for idempotent ops\"]:::green\n end\n\n R1 --- OV\n R2 --- OV\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n classDef teal fill:#38d9a9,stroke:#000,color:#000\n classDef red fill:#ff8787,stroke:#000,color:#000\n```\n\n\nIndices [4] and [5] are covered by both ranges, but since we are computing the minimum (an idempotent operation), the overlap has no effect on the result.\n\n---\n\n## How It Works\n\n### Building the Table\n\nA Sparse Table is a 2D array `table[i][j]` where `table[i][j]` stores the answer (say, the minimum) for the range of length 2^j starting at index i. In other words, `table[i][j]` covers the range [i, i + 2^j - 1].\n\nThe build process uses dynamic programming:\n\n1. **Base case (j = 0):** Every range of length 2^0 = 1 is just a single element. So `table[i][0] = arr[i]` for all i.\n\n1. **Recurrence (j >= 1):** A range of length 2^j can be split into two halves of length 2^(j-1). The first half starts at index i, the second half starts at index i + 2^(j-1).\n\n\n```shell\ntable[i][j] = min(table[i][j-1], table[i + 2^(j-1)][j-1])\n```\n\n\n1. **Bounds:** We build columns j from 1 up to floor(log2(n)). For each j, the starting index i ranges from 0 to n - 2^j (since the range [i, i + 2^j - 1] must fit within the array).\n\nThe total number of entries is approximately n * log2(n), and each entry takes O(1) to compute, giving an overall build time of **O(n log n)**.\n\n\n```mermaid\nflowchart LR\n subgraph Build[\"Building table[i][j] from two halves\"]\n LEFT[\"table[i][j-1]
range [i, i+2^(j-1)-1]\"]:::primary\n RIGHT[\"table[i+2^(j-1)][j-1]
range [i+2^(j-1), i+2^j-1]\"]:::orange\n RESULT[\"table[i][j]
= min(LEFT, RIGHT)
range [i, i+2^j-1]\"]:::green\n end\n\n LEFT --> RESULT\n RIGHT --> RESULT\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n```\n\n\nThis is the same \"combine two halves\" idea that segment trees use, except we are precomputing every possible range rather than building a tree structure.\n\n### Precomputing Log Values\n\nTo answer queries in O(1), we need floor(log2(L)) for any range length L. Computing this on the fly is fine (most languages have a log function), but in competitive programming, floating-point log can introduce subtle precision errors. The standard practice is to precompute an integer log table:\n\n\n```shell\nlog_table[1] = 0\nlog_table[i] = log_table[i / 2] + 1, for i >= 2\n```\n\n\nThis runs in O(n) and gives exact integer values.\n\n### Querying in O(1)\n\nGiven a query range [l, r]:\n\n1. Compute the range length: L = r - l + 1\n2. Find k = floor(log2(L)) using the precomputed log table\n3. The answer is: `min(table[l][k], table[r - 2^k + 1][k])`\n\nThe first range [l, l + 2^k - 1] starts at the left boundary. The second range [r - 2^k + 1, r] ends at the right boundary. Together they cover [l, r], possibly overlapping in the middle. For idempotent operations, this overlap is harmless.\n\n\n```mermaid\nflowchart LR\n subgraph Query[\"Query: min(l, r)\"]\n K[\"k = floor(log2(r-l+1))\"]:::primary\n T1[\"table[l][k]\"]:::orange\n T2[\"table[r-2^k+1][k]\"]:::orange\n ANS[\"Answer = min(T1, T2)\"]:::green\n end\n\n K --> T1\n K --> T2\n T1 --> ANS\n T2 --> ANS\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n```\n\n\n### Why Overlapping Works for Min but Not Sum\n\nThis is a point that trips up many people, so let us be explicit.\n\n- **min(3, 5, 3, 5) = 3.** Including elements twice does not change the minimum. Same for max, GCD, AND, OR. These operations are idempotent: `f(a, a) = a`.\n- **sum(3, 5, 3, 5) = 16, not 8.** Including elements twice doubles their contribution. Sum is not idempotent.\n\nFor non-idempotent operations like sum, you cannot use overlapping ranges. You could still use a Sparse Table, but you would need to decompose the query range into non-overlapping power-of-2 ranges (similar to how a Fenwick Tree decomposes prefix sums). This gives O(log n) query time instead of O(1), which is no better than a Fenwick Tree or segment tree.\n\n**Interview Insight:** If an interviewer asks \"can you use a Sparse Table for range sum queries?\", the answer is \"yes, but the query becomes O(log n) because sum is not idempotent, so you cannot use overlapping ranges.\" This demonstrates genuine understanding versus memorized facts.\n\n---\n\n## Example Walkthrough\n\nLet us build a Sparse Table for the array `arr = [3, 1, 4, 1, 5, 9, 2, 6]` (8 elements, 0-indexed) and then answer a few range minimum queries.\n\n### Step 1: Building the Table\n\n**Column j = 0 (ranges of length 1):**\n\nEach entry is just the element itself.\n\n\n```shell\ntable[0][0] = 3 (range [0, 0])\ntable[1][0] = 1 (range [1, 1])\ntable[2][0] = 4 (range [2, 2])\ntable[3][0] = 1 (range [3, 3])\ntable[4][0] = 5 (range [4, 4])\ntable[5][0] = 9 (range [5, 5])\ntable[6][0] = 2 (range [6, 6])\ntable[7][0] = 6 (range [7, 7])\n```\n\n\n**Column j = 1 (ranges of length 2):**\n\nEach entry combines two adjacent length-1 ranges.\n\n\n```shell\ntable[0][1] = min(table[0][0], table[1][0]) = min(3, 1) = 1 (range [0, 1])\ntable[1][1] = min(table[1][0], table[2][0]) = min(1, 4) = 1 (range [1, 2])\ntable[2][1] = min(table[2][0], table[3][0]) = min(4, 1) = 1 (range [2, 3])\ntable[3][1] = min(table[3][0], table[4][0]) = min(1, 5) = 1 (range [3, 4])\ntable[4][1] = min(table[4][0], table[5][0]) = min(5, 9) = 5 (range [4, 5])\ntable[5][1] = min(table[5][0], table[6][0]) = min(9, 2) = 2 (range [5, 6])\ntable[6][1] = min(table[6][0], table[7][0]) = min(2, 6) = 2 (range [6, 7])\n```\n\n\n**Column j = 2 (ranges of length 4):**\n\nEach entry combines two length-2 ranges.\n\n\n```shell\ntable[0][2] = min(table[0][1], table[2][1]) = min(1, 1) = 1 (range [0, 3])\ntable[1][2] = min(table[1][1], table[3][1]) = min(1, 1) = 1 (range [1, 4])\ntable[2][2] = min(table[2][1], table[4][1]) = min(1, 5) = 1 (range [2, 5])\ntable[3][2] = min(table[3][1], table[5][1]) = min(1, 2) = 1 (range [3, 6])\ntable[4][2] = min(table[4][1], table[6][1]) = min(5, 2) = 2 (range [4, 7])\n```\n\n\n**Column j = 3 (ranges of length 8):**\n\nOnly one range of length 8 fits in an 8-element array.\n\n\n```shell\ntable[0][3] = min(table[0][2], table[4][2]) = min(1, 2) = 1 (range [0, 7])\n```\n\n\n### The Complete Table\n\n\n| i \\ j | 0 | 1 | 2 | 3 |\n|-------|---|---|---|---|\n| 0 | 3 | 1 | 1 | 1 |\n| 1 | 1 | 1 | 1 | - |\n| 2 | 4 | 1 | 1 | - |\n| 3 | 1 | 1 | 1 | - |\n| 4 | 5 | 5 | 2 | - |\n| 5 | 9 | 2 | - | - |\n| 6 | 2 | 2 | - | - |\n| 7 | 6 | - | - | - |\n\n\nEntries marked \"-\" do not exist because the range would extend past the end of the array. The table has n * (floor(log2(n)) + 1) = 8 * 4 = 32 cells, but only 22 are valid. This is consistent with the O(n log n) space claim.\n\n### Step 2: Answering Queries\n\n**Query 1: min(arr[1..6])** (range [1, 6], length 6)\n\n\n```shell\nL = 6 - 1 + 1 = 6\nk = floor(log2(6)) = 2 (since 2^2 = 4 <= 6 < 8 = 2^3)\nRange 1: table[1][2] = 1 (covers [1, 4])\nRange 2: table[6 - 4 + 1][2] = table[3][2] = 1 (covers [3, 6])\nAnswer: min(1, 1) = 1\n```\n\n\nWe can verify: arr[1..6] = [1, 4, 1, 5, 9, 2], and the minimum is indeed 1.\n\n**Query 2: min(arr[4..7])** (range [4, 7], length 4)\n\n\n```shell\nL = 7 - 4 + 1 = 4\nk = floor(log2(4)) = 2 (since 2^2 = 4)\nRange 1: table[4][2] = 2 (covers [4, 7])\nRange 2: table[7 - 4 + 1][2] = table[4][2] = 2 (covers [4, 7])\nAnswer: min(2, 2) = 2\n```\n\n\nNotice that when the range length is exactly a power of 2, both ranges are identical. No wasted work, just a clean lookup.\n\n**Query 3: min(arr[0..2])** (range [0, 2], length 3)\n\n\n```shell\nL = 2 - 0 + 1 = 3\nk = floor(log2(3)) = 1 (since 2^1 = 2 <= 3 < 4 = 2^2)\nRange 1: table[0][1] = 1 (covers [0, 1])\nRange 2: table[2 - 2 + 1][1] = table[1][1] = 1 (covers [1, 2])\nAnswer: min(1, 1) = 1\n```\n\n\nThe overlap here is index 1, which is counted in both ranges. Since min is idempotent, the result is correct. arr[0..2] = [3, 1, 4], minimum is 1.\n\n---\n\n## Implementation\n\n### Java\n\n\n```java\n/**\n * Sparse Table for static Range Minimum Queries.\n * Build: O(n log n) time and space\n * Query: O(1) per query\n */\npublic class SparseTable {\n private int[][] table;\n private int[] logTable;\n private int n;\n\n public SparseTable(int[] arr) {\n n = arr.length;\n int maxLog = Integer.numberOfTrailingZeros(Integer.highestOneBit(n)) + 1;\n\n // Precompute log values\n logTable = new int[n + 1];\n logTable[1] = 0;\n for (int i = 2; i <= n; i++) {\n logTable[i] = logTable[i / 2] + 1;\n }\n\n // Build sparse table\n table = new int[n][maxLog];\n for (int i = 0; i < n; i++) {\n table[i][0] = arr[i];\n }\n\n for (int j = 1; j < maxLog; j++) {\n for (int i = 0; i + (1 << j) - 1 < n; i++) {\n table[i][j] = Math.min(\n table[i][j - 1],\n table[i + (1 << (j - 1))][j - 1]\n );\n }\n }\n }\n\n /**\n * Returns the minimum value in arr[l..r] (inclusive, 0-indexed).\n */\n public int query(int l, int r) {\n int length = r - l + 1;\n int k = logTable[length];\n return Math.min(table[l][k], table[r - (1 << k) + 1][k]);\n }\n}\n```\n\n\n### Python\n\n\n```python\nimport math\n\nclass SparseTable:\n \"\"\"\n Sparse Table for static Range Minimum Queries.\n Build: O(n log n) time and space\n Query: O(1) per query\n \"\"\"\n\n def __init__(self, arr: list[int]):\n n = len(arr)\n self.n = n\n max_log = max(1, math.floor(math.log2(n)) + 1) if n > 0 else 1\n\n # Precompute log values\n self.log_table = [0] * (n + 1)\n for i in range(2, n + 1):\n self.log_table[i] = self.log_table[i // 2] + 1\n\n # Build sparse table\n self.table = [[0] * max_log for _ in range(n)]\n for i in range(n):\n self.table[i][0] = arr[i]\n\n for j in range(1, max_log):\n for i in range(n - (1 << j) + 1):\n self.table[i][j] = min(\n self.table[i][j - 1],\n self.table[i + (1 << (j - 1))][j - 1]\n )\n\n def query(self, l: int, r: int) -> int:\n \"\"\"Returns the minimum value in arr[l..r] (inclusive, 0-indexed).\"\"\"\n length = r - l + 1\n k = self.log_table[length]\n return min(self.table[l][k], self.table[r - (1 << k) + 1][k])\n```\n\n\n### C++\n\n\n```cpp\n#include \n#include \n#include \nusing namespace std;\n\n/**\n * Sparse Table for static Range Minimum Queries.\n * Build: O(n log n) time and space\n * Query: O(1) per query\n */\nclass SparseTable {\n vector> table;\n vector logTable;\n int n;\n\npublic:\n SparseTable(const vector& arr) {\n n = arr.size();\n int maxLog = n > 0 ? __lg(n) + 1 : 1;\n\n // Precompute log values\n logTable.assign(n + 1, 0);\n for (int i = 2; i <= n; i++) {\n logTable[i] = logTable[i / 2] + 1;\n }\n\n // Build sparse table\n table.assign(n, vector(maxLog, 0));\n for (int i = 0; i < n; i++) {\n table[i][0] = arr[i];\n }\n\n for (int j = 1; j < maxLog; j++) {\n for (int i = 0; i + (1 << j) - 1 < n; i++) {\n table[i][j] = min(\n table[i][j - 1],\n table[i + (1 << (j - 1))][j - 1]\n );\n }\n }\n }\n\n // Returns the minimum value in arr[l..r] (inclusive, 0-indexed)\n int query(int l, int r) {\n int length = r - l + 1;\n int k = logTable[length];\n return min(table[l][k], table[r - (1 << k) + 1][k]);\n }\n};\n```\n\n\n---\n\n## Code Explanation\n\nAll three implementations follow the same structure, so let us walk through the logic once.\n\n**The constructor builds the table in two phases.** First, the log table is precomputed using the recurrence `logTable[i] = logTable[i/2] + 1`. This avoids floating-point log calls during queries. Second, the sparse table itself is filled column by column. Column 0 copies the input array directly. Each subsequent column j combines entries from column j-1 using the recurrence: the range [i, i + 2^j - 1] is the minimum of [i, i + 2^(j-1) - 1] and [i + 2^(j-1), i + 2^j - 1].\n\n**The loop bound `i + (1 << j) - 1 < n`** ensures we only compute entries for ranges that fit entirely within the array. This is a common source of off-by-one errors. The condition checks that the last index of the range (i + 2^j - 1) is a valid array index.\n\n**The query method is three lines.** Compute the range length, look up k in the log table, and return the minimum of two overlapping ranges. The bit shift `1 << k` computes 2^k efficiently.\n\n### Common Mistakes\n\n**1. Off-by-one in the build loop.** The inner loop condition must be `i + (1 << j) - 1 < n`, not `i + (1 << j) < n`. The latter computes one fewer entry per column, silently producing wrong results for queries near the end of the array.\n\n**2. Using floating-point log for queries.** Writing `k = (int)(Math.log(length) / Math.log(2))` seems fine, but floating-point imprecision can produce wrong values. For example, `log(8)/log(2)` might return 2.9999999 instead of 3, and casting to int gives 2 instead of 3. Always use an integer log table.\n\n**3. Forgetting to handle length 1 ranges.** When l == r, the length is 1, k = 0, and the query returns `min(table[l][0], table[l][0])`. This works correctly, but make sure your log table handles `logTable[1] = 0`.\n\n**4. Applying the O(1) query to non-idempotent operations.** If you build a Sparse Table for sum and try to use the two-range overlap query, you will double-count elements in the overlap region. For sum queries, you must decompose into non-overlapping power-of-2 ranges.\n\n**5. Incorrect maxLog calculation.** The number of columns needed is floor(log2(n)) + 1. A common error is using `log2(n)` without the +1, which misses the last column and causes out-of-bounds access for queries on the full array.\n\n---\n\n## Complexity Analysis\n\n### Time Complexity\n\n**Build: O(n log n)**\n\nThe table has at most n * (floor(log2(n)) + 1) entries. Each entry is computed in O(1) from two entries in the previous column. The log table precomputation is O(n). So the total build time is O(n log n).\n\n**Query: O(1)**\n\nEach query performs one log table lookup, two table lookups, one min operation, and a few arithmetic operations. All constant time.\n\n### Space Complexity\n\n**O(n log n)**\n\nThe table stores at most n * (floor(log2(n)) + 1) integers. For n = 10^5, this is about 10^5 * 17 = 1.7 * 10^6 entries, roughly 6.8 MB for 32-bit integers. For n = 10^6, it is about 2 * 10^7 entries, roughly 80 MB. This can be tight in memory-constrained environments.\n\nThe log table adds O(n) space, which is dominated by the main table.\n\n### Comparison with Alternatives\n\n\n| Structure | Build Time | Query Time | Update Time | Space | Static Data? |\n|-----------|-----------|------------|-------------|-------|-------------|\n| Sparse Table | O(n log n) | O(1) | N/A | O(n log n) | Yes (required) |\n| Segment Tree | O(n) | O(log n) | O(log n) | O(n) | No (supports updates) |\n| Fenwick Tree | O(n) | O(log n) | O(log n) | O(n) | No (supports updates) |\n| Sqrt Decomposition | O(n) | O(sqrt n) | O(1) | O(n) | No (supports updates) |\n| Naive (no preprocessing) | O(1) | O(n) | O(1) | O(1) | Either |\n\n\nThe trade-off is clear: Sparse Table wins on query time but loses on space and requires static data. Segment trees and Fenwick trees are more flexible. Sqrt decomposition is simpler to implement but slower.\n\n**Interview Insight:** If asked to compare Sparse Table with a segment tree, the key distinction is mutability. Sparse Table: O(1) queries, no updates. Segment tree: O(log n) queries, O(log n) updates. If the interviewer says the data is static, Sparse Table is the better answer. If updates are needed, pivot to a segment tree.\n\n---\n\n## Variations and Extensions\n\n### 2D Sparse Table\n\nThe Sparse Table concept extends to two dimensions for answering range minimum queries on a static 2D matrix. Instead of a 2D table, you build a 4D table: `table[i][j][ki][kj]` stores the minimum in the submatrix from (i, j) to (i + 2^ki - 1, j + 2^kj - 1).\n\nBuild time and space are both O(n * m * log(n) * log(m)), and each query takes O(1) by combining four overlapping submatrices (similar to 2D prefix sum inclusion-exclusion, but with overlapping ranges).\n\nThis is rarely needed in practice, but it appears in competitive programming problems involving static 2D grids.\n\n### Non-Idempotent Operations (Sum, Product)\n\nYou can still build a Sparse Table for sum or product, but you lose the O(1) query. Instead, you decompose the query range [l, r] into non-overlapping power-of-2 ranges by looking at the binary representation of the range length.\n\nFor example, if the range length is 13 = 1101 in binary, you decompose it into ranges of length 8, 4, and 1. This gives O(log n) query time, which is no better than a segment tree. The only benefit is the simpler implementation (no tree structure to manage), but in practice, most people just use a segment tree for non-idempotent operations.\n\n### GCD Sparse Table\n\nGCD is idempotent: gcd(a, a) = a. So the overlapping O(1) query works for range GCD queries. The implementation is identical to range minimum, just replace `min` with `gcd`. This is useful for problems like \"find the GCD of all elements in a subarray\" when the array is static.\n\n### Disjoint Sparse Table\n\nThe Disjoint Sparse Table is a clever variant that supports O(1) queries for **any** associative operation, not just idempotent ones. It works by precomputing answers for ranges that are \"centered\" at specific boundaries, avoiding the overlap issue entirely.\n\nThe build time and space are still O(n log n), and queries are still O(1). The trade-off is a more complex implementation. This is an advanced technique that appears in competitive programming but rarely in interviews.\n\n### Comparison of Variants\n\n\n| Variant | Operations Supported | Query Time | Build Time | Space |\n|---------|---------------------|-----------|------------|-------|\n| Standard Sparse Table | Idempotent (min, max, GCD, AND, OR) | O(1) | O(n log n) | O(n log n) |\n| Non-overlapping decomposition | Any associative (sum, product) | O(log n) | O(n log n) | O(n log n) |\n| 2D Sparse Table | Idempotent on 2D grids | O(1) | O(nm log n log m) | O(nm log n log m) |\n| Disjoint Sparse Table | Any associative | O(1) | O(n log n) | O(n log n) |\n\n\n---\n\n## Comparison with Related Structures\n\nUnderstanding when to use a Sparse Table versus its alternatives is just as important as knowing how it works.\n\n\n| Criterion | Sparse Table | Segment Tree | Fenwick Tree | Sqrt Decomposition |\n|-----------|-------------|--------------|--------------|-------------------|\n| Query time | O(1) | O(log n) | O(log n) | O(sqrt n) |\n| Build time | O(n log n) | O(n) | O(n) | O(n) |\n| Point update | Not supported | O(log n) | O(log n) | O(sqrt n) |\n| Range update | Not supported | O(log n) with lazy | Limited | O(sqrt n) |\n| Space | O(n log n) | O(n) | O(n) | O(n) |\n| Supports min/max | Yes (O(1)) | Yes (O(log n)) | No | Yes (O(sqrt n)) |\n| Code complexity | Simple | Moderate | Simple | Very simple |\n| Static data required? | Yes | No | No | No |\n\n\n### When to Choose Sparse Table\n\n- The data is static (no updates after construction).\n- You need the fastest possible range min/max/GCD queries.\n- The number of queries is very large relative to array size (amortizing the O(n log n) build cost).\n- You are solving LCA via the Euler tour + RMQ reduction and need O(1) LCA queries.\n\n### When NOT to Use Sparse Table\n\n- The data changes. Any single update invalidates the entire table, requiring a full O(n log n) rebuild. If updates happen, use a segment tree instead.\n- Memory is tight. The O(n log n) space can be problematic for very large arrays. A segment tree uses only O(n) space.\n- You need range sum queries. While technically possible with O(log n) query, a Fenwick tree or segment tree is simpler and equally fast.\n- The problem is simple enough for sqrt decomposition. If you do not need O(1) queries and the constraints allow O(sqrt n), sqrt decomposition is much easier to implement and debug.\n\n---\n\n## Common Patterns and Applications\n\n### Pattern 1: Static Range Minimum Query (RMQ)\n\n**Problem type:** Given a static array, answer many queries of the form \"what is the minimum element in the subarray [l, r]?\"\n\n**How Sparse Table helps:** This is the textbook application. Build the Sparse Table once in O(n log n), then answer each query in O(1). No other data structure matches this query performance for static data.\n\n### Pattern 2: LCA via Euler Tour + RMQ\n\n**Problem type:** Given a tree, answer many queries of the form \"what is the Lowest Common Ancestor of nodes u and v?\"\n\n**How Sparse Table helps:** The classic reduction works as follows. Perform an Euler tour of the tree, recording the depth and node at each step. The LCA of u and v corresponds to the node with minimum depth between the first occurrences of u and v in the Euler tour. This is a range minimum query on the depth array. Using a Sparse Table, you get O(n log n) preprocessing and O(1) per LCA query.\n\n\n```mermaid\nflowchart LR\n subgraph Step1[\"1. Euler Tour\"]\n TREE[\"Tree\"]:::primary\n EULER[\"Euler Tour Array
+ Depth Array\"]:::orange\n end\n\n subgraph Step2[\"2. Build Sparse Table\"]\n EULER2[\"Depth Array\"]:::orange\n ST[\"Sparse Table
on depths\"]:::teal\n end\n\n subgraph Step3[\"3. Answer LCA\"]\n Q[\"LCA(u, v)?\"]:::primary\n RMQ[\"RMQ between first
occurrences of u, v\"]:::teal\n ANS[\"O(1) Answer\"]:::green\n end\n\n TREE --> EULER\n EULER2 --> ST\n Q --> RMQ\n RMQ --> ANS\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef teal fill:#38d9a9,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n```\n\n\n### Pattern 3: Sliding Window Minimum/Maximum (Static Variant)\n\n**Problem type:** Given a static array and a fixed window size w, find the minimum in every window of size w.\n\n**How Sparse Table helps:** Build the table once, then for each window position i, query min(arr[i..i+w-1]) in O(1). Total time: O(n log n) build + O(n) queries = O(n log n). A monotonic deque achieves O(n) for this specific problem, but the Sparse Table approach is simpler to code and generalizes to variable-width windows.\n\n### Interview Tips\n\n1. **Identify static data early.** If the problem says \"the array does not change\" or \"all queries are given upfront,\" that is your cue to consider a Sparse Table. Mention this observation to the interviewer before diving into the solution.\n\n1. **Know the idempotent distinction.** The single most important thing about Sparse Tables is that O(1) queries only work for idempotent operations. Being able to explain why (overlapping ranges) and give examples of idempotent vs non-idempotent operations shows deep understanding.\n\n1. **Have the recurrence memorized.** The build recurrence `table[i][j] = min(table[i][j-1], table[i + (1 << (j-1))][j-1])` and the query formula `min(table[l][k], table[r - (1 << k) + 1][k])` are compact enough to memorize. Practice writing them without reference.\n\n1. **Mention the LCA connection.** If the interview involves tree problems, knowing that LCA reduces to RMQ (and that Sparse Table gives O(1) RMQ) shows breadth. Even if you do not implement it, mentioning the connection is valuable.\n\n1. **Compare honestly with segment trees.** Do not oversell Sparse Tables. Acknowledge that segment trees handle a wider range of problems and use less space. Sparse Tables win only in the specific niche of static data with idempotent queries. Interviewers appreciate honest trade-off analysis.\n\n---\n\n## Practice Problems\n\n\n| Problem | Difficulty | Key Concept |\n|---------|------------|-------------|\n| [Static Range Minimum Queries (CSES)](https://cses.fi/problemset/task/1647) | Easy | Direct Sparse Table application |\n| [Range Minimum Query (SPOJ RMQSQ)](https://www.spoj.com/problems/RMQSQ/) | Easy | Classic RMQ on static array |\n| [Longest Common Extension (CF 1535D)](https://codeforces.com/contest/1535/problem/D) | Medium | Sparse Table on LCP array |\n| [LCA using Euler Tour + Sparse Table](https://cses.fi/problemset/task/1688) | Medium | LCA reduction to RMQ |\n| [Range GCD Queries](https://www.spoj.com/problems/GCDSSQ/) | Medium | Sparse Table with GCD instead of min |\n\n\n**Recommended approach:** Start with the two Easy problems to get comfortable with the basic build-and-query pattern. Then tackle the LCA problem to see the Euler tour reduction in action. The GCD problem reinforces that Sparse Tables work for any idempotent operation, not just min/max.\n\n---\n\n## Interview Questions and Answers\n\n**Q1: Why does the Sparse Table query work in O(1) for minimum but not for sum?**\n\n**A:** The O(1) query works by covering the range [l, r] with two overlapping power-of-2 ranges. The overlap means some elements are counted in both ranges. For minimum, this is fine because min is idempotent: min(a, a) = a, so including an element twice does not change the result. Sum is not idempotent: adding an element twice inflates the total. For sum, you must decompose the range into non-overlapping power-of-2 ranges (using the binary representation of the range length), which takes O(log n) time.\n\n---\n\n**Q2: How does the build recurrence `table[i][j] = min(table[i][j-1], table[i + 2^(j-1)][j-1])` work, and why is it correct?**\n\n**A:** The entry `table[i][j]` represents the minimum of the range [i, i + 2^j - 1], which has length 2^j. This range can be split into two equal halves of length 2^(j-1): the left half [i, i + 2^(j-1) - 1] and the right half [i + 2^(j-1), i + 2^j - 1]. The minimum of `table[i][j-1]` (left half) and `table[i + 2^(j-1)][j-1]` (right half) is the minimum of the entire range. This is correct because the two halves are non-overlapping and together cover the full range. The recurrence builds column j from column j-1, so by induction, if column j-1 is correct, column j is correct. The base case (j = 0) copies the array directly, which is trivially correct.\n\n---\n\n**Q3: What is the space overhead of a Sparse Table compared to a Segment Tree, and when does this matter?**\n\n**A:** A Sparse Table uses O(n log n) space: approximately n * (floor(log2(n)) + 1) entries. For n = 10^5, that is about 1.7 million entries. A segment tree uses O(n) space (typically 2n or 4n entries). For n = 10^5, that is 200K to 400K entries. The Sparse Table uses roughly 4-8 times more memory. This matters when n is large (10^6 or more) and memory limits are tight (commonly 256 MB in competitive programming). For n = 10^6 with 32-bit integers, a Sparse Table needs about 80 MB versus a segment tree's 16 MB. In interviews, the space difference is less critical, but mentioning it shows awareness of practical constraints.\n\n---\n\n**Q4: Can a Sparse Table be updated efficiently, or does any change require a full rebuild?**\n\n**A:** A single element change can invalidate up to O(n log n) entries in the table (every entry whose range includes the changed index). There is no efficient way to propagate a single update because the precomputed ranges overlap in complex ways. The only option is a full O(n log n) rebuild. This is the fundamental trade-off: Sparse Tables sacrifice update capability entirely in exchange for O(1) queries. If even occasional updates are needed, a segment tree (O(log n) per update, O(log n) per query) is the right choice.\n\n---\n\n**Q5: How would you use a Sparse Table to find the Lowest Common Ancestor of two nodes in a tree?**\n\n**A:** The classic approach uses the Euler tour reduction. First, perform an Euler tour of the tree, which visits each node multiple times as you enter and leave subtrees. Record two arrays: the node visited at each step, and its depth. Also record the first occurrence of each node in the tour. The LCA of nodes u and v is the node with the minimum depth between the first occurrence of u and the first occurrence of v in the Euler tour. Build a Sparse Table on the depth array. To answer LCA(u, v), find the first occurrences of u and v (call them pos_u and pos_v), then query the range minimum on the depth array between these positions. The node at that minimum-depth position is the LCA. Preprocessing takes O(n log n) for the Sparse Table (the Euler tour itself is O(n)), and each LCA query is O(1).\n\n---\n\n## Summary\n\n### Key Takeaways\n\n- A Sparse Table precomputes answers for all power-of-2 length ranges, enabling O(1) range queries on static data.\n- The O(1) query trick works only for idempotent operations (min, max, GCD, AND, OR) because it relies on overlapping two ranges. For non-idempotent operations like sum, queries degrade to O(log n).\n- Build time and space are both O(n log n). This is more space than a segment tree (O(n)), which is the main downside.\n- Sparse Tables cannot handle updates. Any change requires a full rebuild. If your data changes, use a segment tree or Fenwick tree instead.\n- The most important applications are static RMQ, LCA via Euler tour reduction, and range GCD queries.\n- Always precompute integer log values to avoid floating-point precision issues during queries.\n\n### Quick Reference\n\n\n| Aspect | Details |\n|--------|---------|\n| **Build Time** | O(n log n) |\n| **Query Time** | O(1) for idempotent ops, O(log n) for non-idempotent |\n| **Space** | O(n log n) |\n| **Prerequisites** | Static array (no updates) |\n| **Best For** | Static RMQ, LCA via RMQ, range GCD on immutable data |\n| **Avoid When** | Data changes, memory is tight, or a simpler structure (prefix sum, segment tree) suffices |\n| **Key Formula (Build)** | `table[i][j] = f(table[i][j-1], table[i + 2^(j-1)][j-1])` |\n| **Key Formula (Query)** | `f(table[l][k], table[r - 2^k + 1][k])` where `k = floor(log2(r-l+1))` |\n\n\n---\n\n## References\n\n- [Sparse Table - CP-Algorithms](undefined) - Comprehensive explanation with implementation details and complexity proofs\n- [Range Minimum Query - TopCoder](undefined) - Classic article covering the RMQ-LCA connection\n- [Sparse Table - GeeksforGeeks](undefined) - Beginner-friendly walkthrough with examples\n- [Disjoint Sparse Table - Codeforces Blog](undefined) - Advanced variant supporting non-idempotent operations\n- [Range Minimum Query (Bender and Farach-Colton)](undefined) - Academic paper on the theoretical foundations of RMQ structures","pageType":"dsa"}

Chapter 4: Sparse Table

Ashish Pratap Singh

Get Premium