Problem 58: 2D Range Minimum Query
Problem Statement: Given a 2D matrix, preprocess it to answer queries: for given indices (r1, c1, r2, c2), return the minimum value in the submatrix defined by these coordinates.
Input
The first line contains two integers n and m. The next n lines each contain m integers. Then an integer q is given followed by q lines, each containing four integers: r1, c1, r2, c2.
Output
For each query, print the minimum value in the specified submatrix.
Examples
Input:
3 3
1 2 3
4 5 6
7 8 9
2
1 1 2 2
2 2 3 3
Output:
1
5
Solution Explanation
2D Sparse Table can be built in O(n*m*logn*logm) time and each query answered in O(1). Precompute minima for all submatrices of sizes 2^k by 2^l.
Solution in C++
#include
#include
#include
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector> mat(n, vector(m));
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
cin >> mat[i][j];
}
}
int logn = log2(n) + 1;
int logm = log2(m) + 1;
vector>>> st(logn, vector>>(logm, vector>(n, vector(m))));
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
st[0][0][i][j] = mat[i][j];
}
}
for (int a = 0; a < logn; a++){
for (int b = 0; b < logm; b++){
if(a == 0 && b == 0) continue;
for (int i = 0; i + (1 << a) - 1 < n; i++){
for (int j = 0; j + (1 << b) - 1 < m; j++){
if(a == 0)
st[a][b][i][j] = min(st[a][b-1][i][j], st[a][b-1][i][j + (1 << (b - 1))]);
else if(b == 0)
st[a][b][i][j] = min(st[a-1][b][i][j], st[a-1][b][i + (1 << (a - 1))][j]);
else {
int m1 = min(st[a-1][b-1][i][j], st[a-1][b-1][i + (1 << (a - 1))][j]);
int m2 = min(st[a-1][b-1][i][j + (1 << (b - 1))], st[a-1][b-1][i + (1 << (a - 1))][j + (1 << (b - 1))]);
st[a][b][i][j] = min(m1, m2);
}
}
}
}
}
int q;
cin >> q;
while(q--){
int r1, c1, r2, c2;
cin >> r1 >> c1 >> r2 >> c2;
r1--; c1--; r2--; c2--;
int k1 = log2(r2 - r1 + 1);
int k2 = log2(c2 - c1 + 1);
int m1 = min(st[k1][k2][r1][c1], st[k1][k2][r2 - (1 << k1) + 1][c1]);
int m2 = min(st[k1][k2][r1][c2 - (1 << k2) + 1], st[k1][k2][r2 - (1 << k1) + 1][c2 - (1 << k2) + 1]);
cout << min(m1, m2) << "\n";
}
return 0;
}