A sparse table precomputes the minimum of every window whose length is a power of two. Row k holds the minimums of all windows of length 2**k:
table[k][i] = min(values[i : i + 2**k]), for every i where the window fits, so row k has n - 2**k + 1 entries.
Write build_sparse_table(values) -> list[list[int]] returning the rows k = 0, 1, 2, ... for as long as 2**k <= n. Row 0 is a copy of values. Don't compute each window from scratch: row k comes from row k - 1 in one pass, because a window of length 2**k is two windows of length 2**(k-1) side by side.
build_sparse_table([5, 2, 4, 7, 1, 3])
# [[5, 2, 4, 7, 1, 3], # length 1
# [2, 2, 4, 1, 1], # length 2
# [2, 1, 1]] # length 4
Constraints: 0 <= n <= 10**5; an empty list gives []. The whole build must be O(n log n).
Show hint
table[k][i] = min(table[k-1][i], table[k-1][i + 2**(k-1)]).