2D Sparse Table

For 2D range minimum queries on a matrix: Precompute $\text{st}[r][c][i][j]$ = minimum in rectangle starting at $(r, c)$ with dimensions $2^i \times 2^j$. Query rectangle $(r_1, c_1, r_2, c_2)$:

$1.$ Find $k_r = \log_2(r_2 - r_1 + 1)$, $k_c = \log_2(c_2 - c_1 + 1)$

$2.$ Combine four overlapping rectangles Space: $O(nm \log n \log m)$. Preprocessing: $O(nm \log n \log m)$. Query: $O(1)$. This is useful for problems like "find minimum in any subrectangle" with many queries on a static matrix.