2d sparse table c++
#define vec vector
struct SparseTable2D {
vec<int> log2s;
vec<vec<vec<vec<int>>>> table;
SparseTable2D () = default;
explicit SparseTable2D (const vec<vec<int>>& arr) {
// Preprocess the log 2s
log2s = vec<int>(max(arr.size(), arr[0].size())+1);
for (int i = 2; i<log2s.size(); ++i) {
log2s[i] = log2s[i/2]+1;
}
// Copy input over to the table
table = vec<vec<vec<vec<int>>>>(
(int) log2(arr.size())+1, vec<vec<vec<int>>>(
arr.size(), vec<vec<int>>(
(int) log2(arr[0].size())+1, vec<int>(
arr[0].size()
))));
for (int i = 0; i<arr.size(); ++i) {
for (int j = 0; j<arr[0].size(); ++j) {
table[0][i][0][j] = arr[i][j];
}
// Create each 1D sparse table
auto& cur = table[0][i];
for (int power = 1; power<cur.size(); ++power) {
int prevPower = power-1;
for (int j = 0; j+(1<<power)<=cur[0].size(); ++j) {
cur[power][j] = min(cur[prevPower][j], cur[prevPower][j+(1<<prevPower)]);
}
}
}
for (int iPower = 1; iPower<table.size(); ++iPower) {
int prevPower = iPower-1;
for (int i = 0; i+(1<<iPower)<=table[0].size(); ++i) {
for (int jPower = 0; jPower<table[0][0].size(); ++jPower) {
for (int j = 0; j<table[0][0][0].size(); ++j) {
// Find the minimum of the rectangle made at coord
// (i, j) with a height of iPower and width of jPower
// By taking the min of 1 previous rectangle at the
// same coords but half the height and same width
// and the rectangle with the same dimensions directly
// below it.
table[iPower][i][jPower][j] = min(table[prevPower][i][jPower][j],
table[prevPower][i+(1<<prevPower)][jPower][j]);
}
}
}
}
}
int query (int u, int d, int l, int r) {
int powerY = log2s[d-u+1];
int powerX = log2s[r-l+1];
int lenY = (1<<powerY)-1;
int lenX = (1<<powerX)-1;
int minRow1 = min(table[powerY][u][powerX][l], table[powerY][u][powerX][r-lenX]);
int minRow2 = min(table[powerY][d-lenY][powerX][l], table[powerY][d-lenY][powerX][r-lenX]);
return min(minRow1, minRow2);
}
};