Sparse Table for Matrices

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)$.