Range Minimum Query via Sparse Table
Problem statement
You are given an integer array $A$ of length $n$ (1-indexed: $A[1], A[2], \ldots, A[n]$). You need to build a data structure that, after preprocessing, can answer range minimum queries: given indices $l$ and $r$ with $1 \le l \le r \le n$, return $\min(A[l], A[l+1], \ldots, A[r])$ in $O(1)$ time per query.
Use the sparse table approach:
- Build a 2D table $\text{ST}[i][k]$ that stores the minimum value of the subarray of length $2^k$ starting at index $i$. Formally, $\text{ST}[i][k] = \min(A[i], A[i+1], \ldots, A[i + 2^k - 1])$.
- To answer a query $(l, r)$, decompose it into two (possibly overlapping) blocks of length $2^k$ that together cover $[l, r]$, and return the minimum of the two block minima.
Implement both the preprocessing and query functions. Your solution should use $O(n \log n)$ time and space for preprocessing, and $O(1)$ time per query.
Constraints:
- $1 \le n \le 10^5$
- $-10^9 \le A[i] \le 10^9$
- Up to $10^6$ queries $(l, r)$ with $1 \le l \le r \le n$
Example 1:
- Input: $A = [3, 1, 4, 1, 5, 9, 2, 6]$, query $(2, 7)$
- Output: $1$
- Explanation: $\min(1, 4, 1, 5, 9, 2) = 1$
Example 2:
- Input: $A = [7]$, query $(1, 1)$
- Output: $7$
- Explanation: Single-element array, the minimum is the element itself.
Example 3:
- Input: $A = [5, 5, 5, 5]$, query $(1, 4)$
- Output: $5$
- Explanation: All elements are tied; the minimum is $5$.
You must implement the function range_min(A, queries), where queries is a list of [l, r] pairs (1-based, inclusive). Return the list of range minima, one per query, in order.
Example
range_min([3, 1, 4, 1, 5, 9, 2, 6], [[2, 7]]) -> [1]
The single query asks for the minimum of A[2..7] (1-based) = min(1, 4, 1, 5, 9, 2) = 1, so the returned list is [1]. Note the answer is a list of results, even for one query.
Show hint
Which property of the minimum lets you combine two answers even if they describe overlapping stretches of the array?
Relevant roles: ML Engineer, AI Engineer, Forward Deployed Engineer and LLM Engineer.