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

$ curl repovive.com/roadmaps/data-structures/sparse-tables/sparse-table-for-matrices

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

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

$ curl repovive.com/roadmaps/data-structures/sparse-tables/sparse-table-for-matrices

Repovive

Sparse Table for Matrices - Sparse Tables | Data Structures | Repovive

Repovive.

Data Structures19 sections · 729 units49h total

Open in Course

Sparse Table for Matrices

2D rectangle queries

2D Sparse Table answers rectangle min/max queries.

Precompute $\text{st}[r][c][i][j]$ = answer for rectangle starting at $(r, c)$ with size $2^i \times 2^j$ .

Build by combining four quadrants:

st[r][c][i][j] = min(
    st[r][c][i-1][j-1],
    st[r + 2^(i-1)][c][i-1][j-1],
    st[r][c + 2^(j-1)][i-1][j-1],
    st[r + 2^(i-1)][c + 2^(j-1)][i-1][j-1]
)

Query $(r_1, c_1, r_2, c_2)$ uses four overlapping rectangles.

Space: $O(nm \log n \log m)$ . Build: $O(nm \log n \log m)$ . Query: $O(1)$ .