2D Sparse Table for Rectangle Minimum Queries
A 2D sparse table answers minimum queries on a fixed grid. Indices start at , and queries use inclusive bounds.
The entry stores the minimum in the rectangle starting at with height and width .
Only rectangles that fit inside the grid are stored.
Start with individual cells:
Build the remaining entries in two steps:
In each step, take the minimum of the two halves.
Let and be the top-left and bottom-right corners. The query has height and width
Choose the largest powers of two that fit in these dimensions:
Use four blocks, one at each corner of the query. Let
The blocks start at
Since , the top and bottom blocks cover all query rows. Similarly, , so the left and right blocks cover all query columns. Together, the four blocks cover the whole rectangle.
The blocks may overlap, but repeating cells does not change the minimum. Read their four minima and take the minimum of these values.
There are height levels and width levels. Preprocessing and used space are
Each query takes time.
The global arrays reserve space for the maximum supported grid size. The table alone occupies about MiB.
The grid stays fixed after preprocessing.
#include <bits/stdc++.h>
using namespace std;
const int N = 301;
const int K = 9;
int n, m, lg[N];
long long a[N][N], t[K][K][N][N];
void build() {
for (int i = 2; i <= max(n, m); i++) {
lg[i] = lg[i / 2] + 1;
}
for (int x = 1; x <= n; x++) {
for (int y = 1; y <= m; y++) {
t[0][0][x][y] = a[x][y];
}
}
for (int ky = 1; ky <= lg[m]; ky++) {
int w = 1 << ky;
for (int x = 1; x <= n; x++) {
for (int y = 1; y + w - 1 <= m; y++) {
t[0][ky][x][y] = min(t[0][ky - 1][x][y],
t[0][ky - 1][x][y + w / 2]);
}
}
}
for (int kx = 1; kx <= lg[n]; kx++) {
int h = 1 << kx;
for (int ky = 0; ky <= lg[m]; ky++) {
int w = 1 << ky;
for (int x = 1; x + h - 1 <= n; x++) {
for (int y = 1; y + w - 1 <= m; y++) {
t[kx][ky][x][y] = min(t[kx - 1][ky][x][y],
t[kx - 1][ky][x + h / 2][y]);
}
}
}
}
}
long long get(int x1, int y1, int x2, int y2) {
int kx = lg[x2 - x1 + 1];
int ky = lg[y2 - y1 + 1];
int x = x2 - (1 << kx) + 1;
int y = y2 - (1 << ky) + 1;
return min({t[kx][ky][x1][y1], t[kx][ky][x1][y],
t[kx][ky][x][y1], t[kx][ky][x][y]});
}