这道题我尝试过用一种四叉树写，但是由于复杂度有些高而且常数大，只过了三个点。

所以我用了另一种线段树写法。

先对每一行都建一棵线段树，然后将第 $i$ 行的从第 $j$ 个数到第 $j+n-1$ 个数中最大最小值存到 $Max_{i,j}$ 和 $Min_{i,j}$ 中，然后在对于每一列的 $Max$ 和 $Min$ 数组再建一个线段树，那就能求出每个 $n\times{n}$ 的矩阵中最大数的值和最小数的值了。

当然这种做法并没有二维线段树更灵活。

学线段树学废了？

难度： 蓝

算法： 单调队列，线段树，ST 表等数据结构。

尝试一种二维 ST 表写法。

首先，预处理出 $max_{i,j,k}$ 为以 $(i,j)$ 为左上角，边长 $2^k$ 的正方形中的最大值，$min$ 同理。此处 $k\le n$ 且 $i+2^k-1\le a$，$j+2^k-1\le b$。时间/空间复杂度 $O(ablogn)$。

然后，你就可以在 $O(1)$ 的时间内获得每一个子矩形的最大/最小值了。方法就是把询问的子矩形拆成四个上述已经处理好的正方形，然后合并即可。

注意，如果需要计算 $2$ 的幂次，请使用位运算，而不是 $pow$。后者是带 $log$ 的。

代码量不大，加上许多不必要的卡常操作和注释后也才 $1600B$。

时间复杂度 $O(ablogn)$，遥遥领先。

#include<bits/stdc++.h>
using namespace std;
int n,m,k,ans=1000000000;
int dep=1,len=2,max_st[1010][1010][10],min_st[1010][1010][10];//最大值和最小值的 st 表 
inline int read(){
    int x=0;int ch=getchar();
    while (!isdigit(ch)&&(ch!=EOF)) ch=getchar();
    while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return x;
}//读优
inline int maximum(int a,int b,int c,int d){return max(max(a,b),max(c,d));}//四数最大 
inline int minimum(int a,int b,int c,int d){return min(min(a,b),min(c,d));}//四数最小 
inline int max_que(int x,int y,int d){//查询以 x,y 为左上角边长为 d 的矩阵最大值  
	if(d==1) return max_st[x][y][0];
	int r=log2(d-1),p=1<<r;
	return maximum(max_st[x][y][r],max_st[x+d-p][y][r],max_st[x][y+d-p][r],max_st[x+d-p][y+d-p][r]);
}
inline int min_que(int x,int y,int d){//查询以 x,y 为左上角边长为 d 的矩阵最小值  
	if(d==1) return min_st[x][y][0];
	int r=log2(d-1),p=1<<r;
	return minimum(min_st[x][y][r],min_st[x+d-p][y][r],min_st[x][y+d-p][r],min_st[x+d-p][y+d-p][r]);
}
int main(){
	n=read(),m=read(),k=read();//读入 & 建表 
	for(register int i=1;i<=n;i++){
		for(register int j=1;j<=m;j++){
			min_st[i][j][0]=max_st[i][j][0]=read();
		}
	}
	while(1){
		if(len>=k) break;
		for(register int i=1;i<=n-len+1;i++){
			for(register int j=1;j<=m-len+1;j++){
				max_st[i][j][dep]=max_que(i,j,len);
				min_st[i][j][dep]=min_que(i,j,len);
			}
		}
		dep++,len*=2;
	}
	for(register int i=1;i<=n-k+1;i++){//统计答案 
		for(register int j=1;j<=m-k+1;j++){
			ans=min(ans,max_que(i,j,k)-min_que(i,j,k));
		}
	}
	printf("%d",ans);
}