针对一些二维区间最值问题，用一维ＲＭＱ来解决显然是不够的。所以，要改进算法。鉴于网上没有ＰＡＳＣＡＬ版的ＲＭＱ标程与解析，所以小可在这里简单的讲一下。
核心思想和一维的一样，只是在计算区间时略有不同。用数组Ｆ［ｉ，ｊ，ｋ］表示以ｉ，ｊ为左上角的矩形，长度为（１ ｓｈｌ ｋ），然后在循环时取四个矩形的最值，具体伪代码如下：
for k:=1 to x do ／／ ｘ为要处理矩形的最大边长的ｔｒｕｎｃ（ｌｏｇ２ｍａｘ）值
for i:=1 to n+1-(1 shl k) do
for j:=1 to m+1-(1 shl k) do ／／循环上和一维的一样，只是多加了一层而已
f[i,j,k]:=max(f[i,j,k-1],f[i+1 shl (k-1),j,k-1],f[i,j+1 shl (k-1),k-1],f[i+1 shl (k-1),j+1 shl (k-1),k-1]);
／／ 分成四块正方形计算
查询时和一维的一样，这里不再详讲。
总的时间复杂度为Ｏ（ｌｏｇＮ＊Ｎ２＋Ｍ） 在这里将待处理矩形看做正方形，Ｍ为询问次数
提别提醒：因为循环次数较多，反复调用ｓｈｌ函数会导致常数变大，所以有时可以开一个数组预存要用到的值，以减少时间上的浪费。
＂理想的正方形＂就可以用以上方法完美的解决掉，时间略慢，附上代码
ＡＣ代码：
｛
program zht;
var n,m,s,x,i,j,k,q,w,ans:longint;
f1,f2:array[0..1000,0..1000,0..7] of longint;
z:longint;
function mm(a,b:longint):longint;
begin if a>b then mm:=a else mm:=b;
end;
function max(a,b,c,d:longint):longint;
begin
max:=mm(mm(a,b),mm(c,d));
end;
function mmm(a,b:longint):longint;
begin
if a<b then mmm:=a else mmm:=b; end;
function min(a,b,c,d:longint):longint;
begin
min:=mmm(mmm(a,b),mmm(c,d));
end;
begin
assign(input,'square.in');
assign(output,'square.out');
reset(input);
rewrite(output);
readln(n,m,s);
for i:=1 to n do
for j:=1 to m do
begin
read(z);
f1[i,j,0]:=z;
f2[i,j,0]:=z;
end;
x:=trunc(ln(s)/ln(2));
for k:=1 to x do
for i:=1 to n+1-(1 shl k) do
for j:=1 to m+1-(1 shl k) do
begin
f1[i,j,k]:=max(f1[i,j,k-1],f1[i+1 shl (k-1),j,k-1],f1[i,j+1 shl (k-1),k-1],f1[i+1 shl (k-1),j+1 shl (k-1),k-1]); f2[i,j,k]:=min(f2[i,j,k-1],f2[i+1 shl (k-1),j,k-1],f2[i,j+1 shl (k-1),k-1],f2[i+1 shl (k-1),j+1 shl (k-1),k-1]);
end; ／／ 两个存最值的数组预处理
ans:=maxlongint;
for i:=1 to n-s+1 do
for j:=1 to m-s+1 do
begin
q:=max(f1[i,j,x],f1[i+s-(1 shl x),j,x],f1[i,j+s-(1 shl x),x],f1[i+s-(1 shl x),j+s-(1 shl x),x]);
w:=min(f2[i,j,x],f2[i+s-(1 shl x),j,x],f2[i,j+s-(1 shl x),x],f2[i+s-(1 shl x),j+s-(1 shl x),x]);
ans:=mmm(q-w,ans); ／／ 穷举顶点，计算最小差值
end;
writeln(ans);
close(input);
close(output);
end.
｝
＜Ｍａｒｖｏｌｏ原创，严禁转载＞