function buildSparseTable(arr):
n = arr.length
LOG = floor(log2(n)) + 1
st = 2D array of size n x LOG, filled with 0
// Initialize: ranges of length 1
for i = 0 to n - 1:
st[i][0] = arr[i]
// Fill table: increasing powers of 2
j = 1
while (1 << j) <= n:
i = 0
while i + (1 << j) - 1 < n:
st[i][j] = min(st[i][j-1], st[i + (1 << (j-1))][j-1])
i += 1
j += 1
return st
You iterate through power-of-2 lengths. For each length , you compute all valid starting positions.
Space: for the table.
Time: to fill all entries.