Funcia
Lv.3segment-treesparse-table

Range Minimum Queries

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
0

The altitude at each point of a trail is given by the integer array values, which never changes. For each queries[j] = [l, r], return the minimum of values[l], values[l+1], …, values[r], in query order.

Examples

valuesqueriesresult
[5, 2, 8, 6, 3, 7][[0, 5], [2, 3], [3, 5], [4, 4]][2, 6, 3, 3]
[-1, -1, 0][[1, 2], [0, 0]][-1, -1]

Efficiency

This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.

Function signature

solution(values: int[], queries: int[][]) → int[]

Constraints

  • 1≤N=1 \le N = values.length ≤200,000\le 200{,}000, −109≤-10^9 \le values[i] ≤109\le 10^9
  • 1≤Q=1 \le Q = queries.length ≤200,000\le 200{,}000, 0≤0 \le l ≤\le r <N< N

Expected complexity

Time
O(N log N + Q)
Space
O(N log N)

Examples

valuesqueriesExpected
[5,2,8,6,3,7][[0,5],[2,3],[3,5],[4,4]][2,6,3,3]
[-1,-1,0][[1,2],[0,0]][-1,-1]

Hint

Hint

Build a sparse table t[k][i] = min(values[i .. i + 2^k - 1]) in O(Nlog⁡N)O(N \log N); answer [l, r] with the largest k such that 2k≤r−l+12^k \le r - l + 1 as min(t[k][l], t[k][r - 2^k + 1]) — overlapping halves do not matter for a minimum. A segment tree (O(log⁡N)O(\log N) per query) also works. Scanning every range is O(NQ)O(NQ) and exceeds the time limit.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)222 msestimated
C++ (GCC, gnu++23)222 msderived
Python 3.131000 msderived
Java 252248 msderived
Kotlin 2.4 (JVM)1444 msestimated
C# 14 (.NET 10)1444 msestimated

Test groups

GroupWeightTestsVisibility
sample02inputs and outputs
correctness4010verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.