Sparse Table Build and Query
k = floor(log2(len)). The answer is min of the windows starting at l and ending at r, overlap harmless.
Sparse Table: Query with overlapping windows
5 values fit a window of length 4 = 2^2 and not of 8, so k = 2: use row 2^2.
Cost
- Best
- O(1)
- Average
- O(1)
- Worst
- O(1)
- Space
- O(n log n)
O(n log n) build.
Before this
Taught by the same lesson
Sparse Table covers these too, in the same run.