#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/data-structures/sparse-tables/building-the-table

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/data-structures/sparse-tables/building-the-table

Repovive

Building the Table - Sparse Tables | Data Structures | Repovive

Repovive.

Data Structures19 sections · 729 units49h total

Open in Course

Building the Table

DP construction

def buildSparseTable(arr):
    n = len(arr)
    LOG = int(log2(n)) + 1
    st = [[0] * LOG for _ in range(n)]

    # Initialize: ranges of length 1
    for i in range(n):
        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.