二维 \(\mathcal{ST}\) 表，可以解决二维 \(\mathcal{RMQ}\) 问题。这里不能带修改，如果要修改，就需要二维线段树解决了。

上一道例题吧

类比一维 \(\mathcal{ST}\) 表，我们定义数组 \(f[i][j][k][p]\) 表示从 \((i,j)\) 往下 \(2^k\) 个元素，往右 \(2^p\) 个元素的最值。

建表的话，同样类比一维 \(\mathcal{ST}\) 表，外层两个循环 \(\mathcal{k}\) 和 \(\mathcal{p}\) , 然后内层取最值就行了。要注意的是，\(\mathcal{k}\) 和 \(\mathcal{p}\) 要从 \(0\) 开始循环，因为一行或者一列的情况也要维护。

查询的话，就把一个大矩形分成四个小矩形覆盖住就好了。

空间复杂度 \(\mathcal{O(n^2log^2n)}\)代码在这里

#include
    
     #include
     
      #include
      
       #include
       
        #define N 302int n,T;int val[N][N];int f[N][N][9][9];void prework(){    for(int i=0;i<9;i++){        for(int j=0;j<9;j++){            if(i==0 and j==0) continue;            for(int k=1;k<=n-(1<
       
      
     
    

我们有一种把空间复杂度优化到 \(\mathcal {O(n^2logn)}\) 的方法，记 \(\mathcal{f[i][j][k]}\) 表示以点 \((i,j)\) 为左上角，边长为 \(\mathcal{2^k}\) 的正方形所要维护的最值。

考虑查询，设查询矩形的左上角和右下角坐标分别为 \((r1,c1)\) 和 \((r2,c2)\)。且假设 \(r2-r1>c2-c1\)。

因为我们维护的是一个正方形内的最值，所以不能 \(\mathcal{O(1)}\) 的查询。而是要这样

for(int i=r1;i<=r2-(1<

其实这样是能被一个宽度为 \(1\) 的长方形把查询复杂度卡成 \(O(n)\) 的，但毕竟空间复杂度小了一个 \(\mathcal{log}\) 倍，对于一些内存紧张的题目，这种做法还是能起到一定效果的。

下面是 \(\mathcal{ZOJ}\) \(2859\) 第二种做法的代码。

上一下两种方法的对比吧，大家自行比较选择。

第一种：

第二种：

#include
    
     #include
     
      #include
      
       #include
       
        #define N 302int T;int n;int val[N][N];int f[N][N][9];void prework(){    for(int i=1;i<9;i++){        for(int k=1;k<=n-(1<