二维ST表（查询子矩阵最值问题）

· · 算法·理论

前置知识：一维 ST 表

定义 dp_{i,j,k,l} 为以 (i, j) 为左上角，长为 2^l，宽为 2^k 的最值。

令 x = 2^{k - 1}，y = 2 ^ {l - 1}。

参考上图，显然有：

dp_{i,j,k,l} = \max (dp_{i,j,k-1,l-1},dp_{i,j+y,k-1,l-1},dp_{i+x,j,k-1,l-1},dp_{i+x,j+y,k-1,l-1})

令 x = 2^{k}，y = 2 ^ {l}。

对于每次查询子矩阵 (sx,sy),(ex, ey) 的最值（参考上图），显然为：\max(dp_{sx,sy,k,l},dp_{ex-x+1,sy,k,l},dp_{sx,ey-y+1,k,l},dp_{ex-x+1,ey-y+1,k,l})

注意：需要预处理 dp_{i,j,k,0} 和 dp_{i,j,0,l} 的值。

void initSt() {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) dp[i][j][0][0] = a[i][j];
    }

    for (int k = 1; k <= 11; k++) {
        for (int i = 1; i + (1 << k) - 1 <= n; i++) {
            for (int j = 1; j <= m; j++) {
                dp[i][j][k][0] = max(dp[i][j][k - 1][0], dp[i + (1 << k - 1)][j][k - 1][0]);
            }
        }
    }
    for (int l = 1; l <= 11; l++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j + (1 << l) - 1 <= m; j++) {
                dp[i][j][0][l] = max(dp[i][j][0][l - 1], dp[i][j + (1 << l - 1)][0][l - 1]);
            }
        }
    }

    for (int k = 1; k <= 11; k++) {
        for (int l = 1; l <= 11; l++) {
            for (int i = 1; i + (1 << k) - 1 <= n; i++) {
                for (int j = 1; j + (1 << l) - 1 <= m; j++) {
                    int x = 1 << k - 1, y = 1 << l - 1;
                    //     i             j
                    dp[i][j][k][l] = max({
                        dp[i][j][k - 1][l - 1],
                        dp[i][j + y][k - 1][l - 1],
                        dp[i + x][j][k - 1][l - 1],
                        dp[i + x][j + y][k - 1][l - 1]
                    });
                }
            }
        }
    }
}

int query(int sx, int sy, int ex, int ey) {
    int k = LOG2[ex - sx + 1], l = LOG2[ey - sy + 1];
    return max({
        dp[sx][sy][k][l],
        dp[ex - (1 << k) + 1][sy][k][l],
        dp[sx][ey - (1 << l) + 1][k][l],
        dp[ex - (1 << k) + 1][ey - (1 << l) + 1][k][l]
    });
}