2017. Range Minimum When Nothing Changes
An array of n integers is given, numbered from 1, and it NEVER changes. Then
q queries arrive, each a pair l r: print the smallest value in positions l
through r inclusive.
``` 3 1 4 1 5
1 5 -> 1 2 3 -> 1 4 4 -> 1 ```
## What most people try first
The segment tree from problem 2004. It is correct and it is O(log n) per
query, which is fine. The question worth asking is what the problem gives you
that 2004 did not: the array never changes. Paying for a structure that supports
updates, when no update can arrive, is leaving something on the table.
Scanning each range is O(n) per query, so 2 * 10^5 queries over
2 * 10^5 values is 4 * 10^10 comparisons.
## Precompute every power-of-two window
Let sp[j][i] be the minimum of the 2^j values starting at i. Each level
builds from the one below by overlapping two half-length windows:
sp[0][i] = a[i]
sp[j][i] = min( sp[j-1][i], sp[j-1][i + 2^(j-1)] )
That is O(n log n) to build and the same in memory: about 3.6 * 10^6
entries at n = 2 * 10^5.
## Answer in constant time with two overlapping windows
Let k be the largest power of two that fits in the range, so
2^k <= r - l + 1. Then two windows of length 2^k, one anchored at each end,
cover the range completely:
k = floor(log2(r - l + 1))
answer = min( sp[k][l], sp[k][r - 2^k + 1] )
They OVERLAP, usually heavily, and that is the whole trick. A minimum does not care how many times a value is counted, so overlapping is free. This is exactly why the method works for minimum, maximum and gcd but NOT for a sum: counting a value twice changes a sum, so a sum needs disjoint pieces and cannot be answered in two lookups.
## The boundary
A query where l equals r has length 1, so k is 0 and both windows are the
single element. Computing k with a floating-point logarithm is where this
breaks: log2(8) can come back as 2.9999999999999996, giving k = 2 instead of
3, which still answers correctly here but silently reads the wrong windows in
problems where the length matters. Use the bit length of the integer instead.
## Cost
O(n log n) to build, then O(1) per query: two array reads and a comparison,
whatever the range length.
Constraints - `1 ≤ n ≤ 200000` - `1 ≤ q ≤ 200000` - `-10^9 ≤ each value ≤ 10^9` - `1 ≤ l ≤ r ≤ n` - the array never changes
Input
The first line contains two integers n and q.
The second line contains n integers.
Each of the next q lines contains two integers l and r.
Output
Print one integer on its own line for each query, in the order given: the smallest value in positions l through r inclusive.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.