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

$ curl repovive.com/roadmaps/data-structures/sparse-tables/power-of-2-ranges

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

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

$ curl repovive.com/roadmaps/data-structures/sparse-tables/power-of-2-ranges

Repovive

Power-of-2 Ranges - Sparse Tables | Data Structures | Repovive

Repovive.

Data Structures19 sections · 729 units49h total

Open in Course

Power-of-2 Ranges

The building blocks

Sparse Table precomputes $\text{st}[i][j]$ = answer for range starting at index $i$ with length $2^j$ .

st[i][0] = arr[i]           # length 1
st[i][1] = min(st[i][0], st[i+1][0])  # length 2
st[i][2] = min(st[i][1], st[i+2][1])  # length 4
...
st[i][j] = min(st[i][j-1], st[i + 2^(j-1)][j-1])

Each entry combines two half-size ranges:

Range $[i, i + 2^j - 1]$ combines $[i, i + 2^{j-1} - 1]$ and $[i + 2^{j-1}, i + 2^j - 1]$

Total entries: $O(n \log n)$ . Each computed in $O(1)$ .

Preprocessing time: $O(n \log n)$ .