Building the Table

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 $2^j$, you compute all valid starting positions.

Space: $O(n \log n)$ for the table.

Time: $O(n \log n)$ to fill all entries.