摘要
我们知道一维的st表在经过预处理后可以在O(1)时间内查询任意区间的极值，虽然其是离线算法，但胜在代码短小易写。而在二维RMQ（区间最值查询）问题中，我们依然可以采用st算法解决问题，只不过我们需要从一维拓展到二维，当然适用范围依然是离线。二维st表仍然是用倍增思想，如果理解了一维的st表，那么对于二维的也不难理解。
问题描述
给定一个n* n的矩阵以及一个整数b和k，共有k次询问，每次询问给出边长为b的子矩阵的左上角的行和列(r,c)，请回答该子矩阵内的最大值和最小值的差是多少。
算法思路
变量定义：
st[r][c][k]存放以(r , c)为左上角的边长为 2 k 2^k 2k个元素的矩阵的最大值。
a[n][n]用来存放矩阵中的元素。
查询操作：
假设我们的st表已经更新完毕，此时st[r][c][k]中存放的是以(r , c)为左上角的边长为 2 k 2^k 2k 的矩阵内的最大值，那么对于一个查询(a , b , c) 即查询以(a , b)为左上角，边长为 c 的矩阵内的最大值该如何处理呢？
显然和一维一样，由于我们的st表中存放的区间长度是2的次方项，因此如果边长并不恰好是2的次方项，那么就无法通过一次访问st表求得，需要通过几个重叠区间得出结果。在二维RMQ中，就体现为将一个大矩阵查询分为4个小矩阵查询。
下面我们具体来讲一下如何划分查询区间。假设我们要查询的是以（a，b）为左上角，边长为 c 的矩阵内的最大值，那么假设 k = l o g 2 c k = log_2^c k=log2c 向下取整，那么显然st[a][b][k]是一个如下图(a)中显示的一个小矩阵。
那么显而易见，st[a][b+c-(1<<k)+1][k]正如（b）中的蓝色矩形一样覆盖了以右上角为顶点的矩阵。同理，我们共需要四个矩形来覆盖整个大矩形，如（c）所示。因此对于任意边长的正方形，我们都可以计算出其覆盖面积的最大值。因为求极值操作是允许区间重叠的( [1 , 10] 的最大值可以由[1 , 6] 的最大值和[2 , 10]的最大值得出 )，因此上述划分方法虽有区间重叠，但对最终答案没有影响（求和则不行）。
总结起来，若设最终要求的答案为ans，则：
令t1 = st[a][b][c];
令t2 = st[a][b+c-(1<<k)+1][c];
令t3 = st[a+c-(1<<k)+1][b][c];
令t4 = st[a+c-(1<<k)+1][b+c-(1<<k)+1][c];
ans = max{t1 , t2 , t3 , t4}；
因此我们得证了，利用上述定义的st表，确实可以在常数时间内求出目标矩阵的最大值。
更新st表（预处理）
我们在一开始就提到过，st表是离线算法， 即不支持修改操作，因此以此预处理之后便只能进行查询。预处理时间复杂度为 O ( N 2 l o g 2 N ) O(N^2log_2N) O(N2log2N)。预处理用到了动态规划的思想。
更新也是同样的道理，更新一个大矩形，需要用到4个小矩形。状态转移方程如下：
st[i][j][k] = Max( st[i][j][k-1] , st[i+(1<<k-1)][j][k-1] , st[i][j+(1<<k-1)][k-1] , st[i+(1<<k-1)][j+(1<<k-1)][k-1]);
为什么这个式子成立呢？如果从式子上看， 2 k − 1 + 2 k − 1 = 2 k 2^{k-1} + 2^{k-1} = 2^k 2k−1+2k−1=2k，因此俩个小区间可以更新一个大区间，拓展到二维上呢，就是4个小矩阵更新一个大矩阵。如果用图来描述，就如（d）所示，四个小矩形构成一个大矩形，而大矩形的边长是小矩形的2倍。于是我们就可以通过四个小矩阵的值来更新大矩阵的值。
例题 HAOI2007理想的正方形
解题思路：
本题就是一个二维RMQ问题的裸题，和上述模型不同的是，其是一个长a宽b的矩形，而非正方形。不管是矩形还是正方形，我们的更新和查询都是划分为4个子矩阵来更新或查询，因此只需对代码稍作改变即可，基本没太大变化，预处理都是 O ( N 2 l o g N ) O(N^2logN) O(N2logN)，查询也都是O(1)。
代码示例：
#include<cstdio>
const int N = 1010;
int a[N][N],n,m,len,Log[N];
int st[3][N][N][15];//0最小，1最大值
int max(int a,int b,int c,int d){int mx = a;if(mx < b) mx = b;if(mx < c) mx = c;if(mx < d) mx = d;return mx;
}
int min(int a,int b,int c,int d){int mi = a;if(mi > b) mi = b;if(mi > c) mi = c;if(mi > d) mi = d;return mi;
}
void init(){for(int i = 2;i < N;i++) Log[i] = Log[i/2]+1;for(int i = 1;i <= n;i++)for(int j = 1;j <= m;j++) st[0][i][j][0] = st[1][i][j][0] = a[i][j];for(int k = 1;k <= 12;k++){for(int i = 1;i + (1<<k)-1 <= n;i++){for(int j = 1;j + (1<<k)-1 <= m;j++){int t1 = st[0][i][j][k-1];int t2 = st[0][i+(1<<(k-1))][j][k-1];int t3 = st[0][i][j+(1<<(k-1))][k-1];int t4 = st[0][i+(1<<k-1)][j+(1<<k-1)][k-1];st[0][i][j][k] = min(t1,t2,t3,t4);t1 = st[1][i][j][k-1];t2 = st[1][i+(1<<(k-1))][j][k-1];t3 = st[1][i][j+(1<<(k-1))][k-1];t4 = st[1][i+(1<<k-1)][j+(1<<k-1)][k-1];st[1][i][j][k] = max(t1,t2,t3,t4);}}}
}
int ask(int r,int c,int len){int k = Log[len];int t1 = st[0][r][c][k];int t2 = st[0][r+len-(1<<k)][c][k];int t3 = st[0][r][c+len-(1<<k)][k];int t4 = st[0][r+len-(1<<k)][c+len-(1<<k)][k];int mi = min(t1,t2,t3,t4);t1 = st[1][r][c][k];t2 = st[1][r+len-(1<<k)][c][k];t3 = st[1][r][c+len-(1<<k)][k];t4 = st[1][r+len-(1<<k)][c+len-(1<<k)][k];int mx = max(t1,t2,t3,t4);//printf("%d %d\n",mx,mi);return mx - mi;
}
int main(){scanf("%d%d%d",&n,&m,&len);for(int i = 1;i <= n;i++)for(int j = 1;j <= m;j++) scanf("%d",&a[i][j]);init();int ans = 0x3f3f3f3f;for(int i = 1;i <= n-len+1;i++){for(int j = 1;j <= m-len+1;j++){int tmp = ask(i,j,len);ans = ans < tmp?ans:tmp;}}printf("%d\n",ans);return 0;
}
结束语
大家可以发现我们的二维st表建立在正方形矩阵查询的基础上的，因此st表仅三个维度，即st[r][c][k]代表以(r , c) 为左上角的边长为 2 k 2^k 2k的矩阵的极值；但如果所给矩阵以及所求矩阵并不是正方形而是普通矩形，那就要增加一个维度，即st[r][c][k1][k2]表示以（r，c）为左上角，长为 2 k 1 2^{k1} 2k1高为 2 k 2 2^{k2} 2k2的矩阵的极值，其更新方法与本文所介绍的类似，都是通过4个子矩阵来更新，查询也是通过4个子矩阵来查询最终答案。
