矩阵最值

GitHub跳转原题关系图返回列表

对矩阵做二维稀疏表:先按行合并再按列合并,每次询问用四个 2^a×2^b 方块 O(1) 完全覆盖矩形取最大值。

OJ: roj

题目 ID: 1746

难度:提高

标签:数据结构RMQ稀疏表二维python

创建: 2026-10-07 21:06

更新: 2026-10-07 21:06

形式化题目

给定一个 nn 行 mm 列的矩阵 AA(11 起始下标),值域 0⩽Ai,j<2310 \leqslant A_{i,j} < 2^{31}。 有 KK 次询问,第 tt 次给出 (x1,y1,x2,y2)(x_1, y_1, x_2, y_2) 且保证 x1⩽x2,  y1⩽y2x_1 \leqslant x_2,\; y_1 \leqslant y_2, 要求输出

max⁡{ Ai,j∣x1⩽i⩽x2,  y1⩽j⩽y2 }. \max\{\,A_{i,j} \mid x_1 \leqslant i \leqslant x_2,\; y_1 \leqslant j \leqslant y_2\,\}.

数据范围:

档位 n,mn, m KK
30%30\% ⩽50\leqslant 50 ⩽103\leqslant 10^3
50%50\% ⩽250\leqslant 250 ⩽104\leqslant 10^4
100%100\% ⩽250\leqslant 250 ⩽106\leqslant 10^6

注意询问矩形的高度 Lx=x2−x1+1L_x = x_2 - x_1 + 1 与宽度 Ly=y2−y1+1L_y = y_2 - y_1 + 1 都是任意的, 并不要求是 22 的幂,也不要求查询次数与矩阵大小同阶——正是 KK 高达 10610^6 这一点把"每次询问都扫一遍矩形"的写法彻底排除掉了。

正解

思路

朴素做法为什么不行。 最直接的想法是每次询问都双重循环扫矩形, 最坏情况下单个矩形就有 n×m=62500n \times m = 62500 个格子,乘上 K=106K = 10^6 次询问, 总运算量约 6×10106 \times 10^{10},无论怎么常数优化都过不去。

从一维 RMQ 说起。 一维的"区间最大值"是稀疏表(ST 表)的模板: 预处理 st[k][i] = max(A[i..i+2^k-1]),递推式

stk[i]=max⁡(stk−1[i],  stk−1[i+2k−1]), st_k[i] = \max\bigl(st_{k-1}[i],\; st_{k-1}[i + 2^{k-1}]\bigr),

预处理 O(nlog⁡n)O(n \log n),询问 O(1)O(1)。之所以询问能 O(1)O(1),靠的是这样一条性质:

覆盖引理. 设 L⩾1L \geqslant 1,取 a=⌊log⁡2L⌋a = \lfloor \log_2 L \rfloor,则区间 [l,l+L−1][l, l+L-1] 被两个长度都是 2a2^a 的区间 [l,l+2a−1][l, l+2^a-1] 与 [l+L−2a,l+L−1][l+L-2^a, l+L-1] 完全覆盖,即它们的并集恰好等于整个区间。

证明只需注意 2a⩽L<2a+12^a \leqslant L < 2^{a+1}:左块从 ll 起盖到 l+2a−1l + 2^a - 1, 右块从 l+L−2al + L - 2^a 起盖到 l+L−1l+L-1,而 l+L−2a⩽l+2al + L - 2^a \leqslant l + 2^a 说明两块 之间没有空隙。于是"两块的 max"就等于"整段的 max"——允许重叠, 这正是 ST 表能做到 O(1)O(1) 而不是 O(log⁡)O(\log) 的原因。

推广到二维。 把行方向与列方向各用一次覆盖引理,矩形就被四个方块盖住。 设 Lx=x2−x1+1L_x = x_2 - x_1 + 1、Ly=y2−y1+1L_y = y_2 - y_1 + 1,令

a=⌊log⁡2Lx⌋,b=⌊log⁡2Ly⌋, a = \lfloor \log_2 L_x \rfloor, \qquad b = \lfloor \log_2 L_y \rfloor,

则高度为 2a2^a 的行区间只需两个(起点 x1x_1 与 x2−2a+1x_2 - 2^a + 1), 宽度为 2b2^b 的列区间也只需两个(起点 y1y_1 与 y2−2b+1y_2 - 2^b + 1), 行列组合起来正好是四个 2a×2b2^a \times 2^b 的方块:

ans=max⁡u∈{x1,x2−2a+1}v∈{y1,y2−2b+1}blk[a][b][u][v]. \text{ans} = \max_{\substack{u \in \{x_1,\; x_2 - 2^a + 1\} \\ v \in \{y_1,\; y_2 - 2^b + 1\}}} \mathrm{blk}[a][b][u][v].

它们同样允许重叠,并集覆盖整个询问矩形,所以取 max 是安全的。

预处理怎么递推。 直接对二维写四象限递推当然可以,但更省事、也更省常数的做法是 把两个方向拆开:

  1. 行方向合并。记 rowst[a][i][j] 表示从第 ii 行起共 2a2^a 行、只取第 jj 列这一竖条的最大值:
rowsta[i][j]=max⁡(rowsta−1[i][j],  rowsta−1[i+2a−1][j]). rowst_a[i][j] = \max\bigl(rowst_{a-1}[i][j],\; rowst_{a-1}[i + 2^{a-1}][j]\bigr).
  1. 列方向合并。在固定的 aa 层上再对列做一次同样的合并,得到真正的方块表:
blk[a][b][i][j]=max⁡(blk[a][b−1][i][j],  blk[a][b−1][i][j+2b−1]). blk[a][b][i][j] = \max\bigl(blk[a][b-1][i][j],\; blk[a][b-1][i][j + 2^{b-1}]\bigr).

这样每次合并都是"两个等长数组逐位取 max",实现上就是两次切片 + map(max, ...), 比四象限版本少一半常数。需要留意的是有效下标的范围: rowst[a] 只有 i⩽n−2ai \leqslant n - 2^a 的行是合法的,blk[a][b] 只有 i⩽n−2ai \leqslant n - 2^a、j⩽m−2bj \leqslant m - 2^b 的位置合法。这不是缺陷——由覆盖引理, 查询时用到的四个方块的左上角恰好都落在这个合法范围内,所以其余位置填 00 永不参与计算。

关于值域。 Ai,j<231A_{i,j} < 2^{31},最大值不超过 21474836472147483647,刚好塞进 32 位有符号 int,因此 C++ 侧全程用 int 即可,不需要 long long;Python 侧更是无所谓。

代码

Python 版本与 C++ 版本算法完全一致:同样是 O(nmlog⁡nlog⁡m)O(n m \log n \log m) 的预处理加 O(1)O(1) 询问,只是把"逐元素循环"换成切片 + map(max, ...) 的整行/整列操作。 n=m=250n = m = 250 时预处理一共只有 9×9×62500≈5×1069 \times 9 \times 62500 \approx 5 \times 10^6 个 元素,Python 也能在数秒内建完表。

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-07 20:58
# update_at: 2026-10-07 21:06

import sys

# 类型别名(Python 3.12+ 的 type 语句),相当于 C++ 的 using / typedef
type Table = list[int]        # 一维展开(行优先)的 n x m 表,下标 i*m+j
type Levels = list[Table]     # 固定行跨度 a 时,列跨度 b = 0,1,2,... 的各层表

FLUSH = 1 << 16               # 输出攒够这么多行就落盘,避免 1e6 个字符串同时驻留


def row_levels(n: int, m: int, base: Table, la: int) -> Levels:
    """行方向稀疏表:lv[a][i*m+j] = max{ base[i'][j] : i <= i' < i + 2^a }。"""
    lv = [base]
    for a in range(1, la):
        half = 1 << (a - 1)
        span = half << 1
        prev = lv[-1]
        cur = [0] * (n * m)
        # 只有 i + 2^a <= n 的行能放下一个完整的 2^a 行块,其余位置永远查不到
        for i in range(n - span + 1):
            lo = i * m
            hi = (i + half) * m
            cur[lo:lo + m] = map(max, prev[lo:lo + m], prev[hi:hi + m])
        lv.append(cur)
    return lv


def col_levels(n: int, m: int, rows: Table, lb: int) -> Levels:
    """在某一 a 层上做列方向合并:lv[b][i*m+j] = max{ rows[i*m+j'] : j <= j' < j + 2^b }。"""
    lv = [rows]
    for b in range(1, lb):
        half = 1 << (b - 1)
        span = half << 1
        prev = lv[-1]
        cur = [0] * (n * m)
        width = m - span + 1  # 列方向同理,只有前 width 列能放下完整的 2^b 列块
        for i in range(n):
            lo = i * m
            cur[lo:lo + width] = map(max, prev[lo:lo + width], prev[lo + half:lo + half + width])
        lv.append(cur)
    return lv


def build_tables(n: int, m: int, grid: Table) -> list[Levels]:
    """二维稀疏表:tab[a][b][i*m+j] 是以 (i,j) 为左上角的 2^a 行 x 2^b 列方块的最大值。"""
    la, lb = n.bit_length(), m.bit_length()  # 2^(la-1) <= n < 2^la,即楼层数 = log2(n)+1
    return [col_levels(n, m, rows, lb) for rows in row_levels(n, m, grid, la)]


def solve() -> None:
    data = sys.stdin.buffer
    n, m, K = map(int, data.readline().split())

    grid: Table = []
    while len(grid) < n * m and (line := data.readline()):  # 矩阵可能跨行,读满 n*m 个数
        grid += map(int, line.split())
    tab = build_tables(n, m, grid)

    write = sys.stdout.write
    out: list[str] = []
    for _ in range(K):
        x1, y1, x2, y2 = map(int, data.readline().split())
        height, width = x2 - x1 + 1, y2 - y1 + 1
        # 2^a x 2^b 的方块只要四个角各放一块,就能完全盖住整个询问矩形
        a, b = height.bit_length() - 1, width.bit_length() - 1
        t = tab[a][b]
        dr = height - (1 << a)  # 下方方块相对左上角方块的行偏移(0 表示高度恰是 2 的幂)
        dc = width - (1 << b)   # 右方方块相对左上角方块的列偏移
        lt = (x1 - 1) * m + y1 - 1   # 左上角方块的下标
        lbot = lt + dr * m           # 左下角方块的下标
        best = max(t[lt], t[lt + dc], t[lbot], t[lbot + dc])
        out.append(str(best))
        if len(out) == FLUSH:
            write('\n'.join(out))
            write('\n')
            out.clear()

    if out:
        write('\n'.join(out))
        write('\n')


if __name__ == "__main__":
    solve()

C++ 版本带快速读入与快速输出(K⩽106K \leqslant 10^6,输入输出本身就有几 MB), 表按 (a, b) 分块存放,保证一次询问的四次查表都落在同一块连续内存里。

cpp
// 一本通 1746《矩阵最值》 —— 二维稀疏表(ST 表)
//
// 题意:给定 n 行 m 列的矩阵,K 次询问,每次问以 (x1,y1) 为左上角、
//       (x2,y2) 为右下角的子矩阵的最大值。
//       数据范围:n, m <= 250,K <= 10^6,0 <= a[i][j] < 2^31。
//
// 算法:二维 ST 表。
//   记 st[a][b] 为「2^a 行 x 2^b 列」的方块最大值表:
//       st[a][b][i][j] = max{ a[i'][j'] : i <= i' < i + 2^a, j <= j' < j + 2^b }。
//   为省内存并保持缓存友好,不直接四象限递推,而是分成两步:
//     1) 行方向合并,得到只含行信息的 rowst[a] = st[a][0];
//     2) 在 rowst[a] 上做列方向合并,依次得到 st[a][1], st[a][2], ...
//   询问 O(1):设询问矩形有 Lx 行 Ly 列,令 a = floor(log2 Lx)、b = floor(log2 Ly),
//   则四个角上的 2^a x 2^b 方块(左上、右上、左下、右下)恰好完全覆盖整个矩形,
//   取四者最大值即为答案。
//
// 复杂度:时间 O(n*m*log n*log m + K),空间 O(n*m*log n*log m)。
//        本题 n=m=250 时预处理约 5e6 次取 max,查询 4 次查表,非常宽裕。
//
// 编译:/opt/homebrew/bin/g++-16 -O2 -std=c++17 -Wall -Wextra
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

// ---------------- 快速读入 ----------------
static const int IBUF = 1 << 22;
static char ibuf[IBUF];
static int ilen = 0, ipos = 0;

static inline int gc() {
    if (ipos == ilen) {
        ilen = (int)fread(ibuf, 1, IBUF, stdin);
        ipos = 0;
        if (ilen <= 0) return -1;
    }
    return (unsigned char)ibuf[ipos++];
}

// 读入一个非负整数(题面保证 0 <= a[i][j] < 2^31,int 足够)
static inline int readInt() {
    int c = gc();
    while (c != -1 && (c < '0' || c > '9')) c = gc();
    int v = 0;
    while (c >= '0' && c <= '9') {
        v = v * 10 + (c - '0');
        c = gc();
    }
    return v;
}

// ---------------- 快速输出 ----------------
static const int OBUF = 1 << 22;
static char obuf[OBUF];
static int opos = 0;

static inline void wch(char c) {
    if (opos == OBUF) {
        fwrite(obuf, 1, OBUF, stdout);
        opos = 0;
    }
    obuf[opos++] = c;
}

static inline void wInt(int v) {
    char tmp[12];
    int t = 0;
    if (v == 0) tmp[t++] = '0';
    while (v > 0) {
        tmp[t++] = (char)('0' + v % 10);
        v /= 10;
    }
    while (t > 0) wch(tmp[--t]);
    wch('\n');
}

// ---------------- 全局变量 ----------------
const int MAXN = 250;   // 行数上限
const int MAXM = 250;   // 列数上限
const int MAXL = 9;     // log2(250) + 1

int n, m, K;
int lg2[MAXM + 1];      // lg2[x] = floor(log2 x)

// tab[a * LB + b] 是一维展开(行优先)的 n x m 表,表示 2^a 行 x 2^b 列的方块最大值
vector<vector<int>> tab;
int LA, LB;

int main() {
    n = readInt();
    m = readInt();
    K = readInt();

    int mx = max(n, m);
    for (int i = 2; i <= mx; i++) lg2[i] = lg2[i >> 1] + 1;
    LA = lg2[n] + 1;
    LB = lg2[m] + 1;

    tab.assign((size_t)LA * LB, vector<int>());

    // 第 0 层:原矩阵
    vector<int> &base = tab[0];
    base.assign((size_t)n * m, 0);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) base[(size_t)i * m + j] = readInt();

    // 先做行方向合并:tab[a*LB + 0] 表示 2^a 行 x 1 列的最大值
    for (int a = 1; a < LA; a++) {
        vector<int> &cur = tab[(size_t)a * LB];
        cur.assign((size_t)n * m, 0);
        const vector<int> &prv = tab[(size_t)(a - 1) * LB];
        int half = 1 << (a - 1);
        int span = 1 << a;
        for (int i = 0; i + span <= n; i++) {
            const int *p0 = &prv[(size_t)i * m];
            const int *p1 = &prv[(size_t)(i + half) * m];
            int *pc = &cur[(size_t)i * m];
            for (int j = 0; j < m; j++) pc[j] = p0[j] > p1[j] ? p0[j] : p1[j];
        }
    }

    // 再做列方向合并:由 tab[a*LB + b-1] 得到 tab[a*LB + b]
    for (int a = 0; a < LA; a++) {
        for (int b = 1; b < LB; b++) {
            vector<int> &cur = tab[(size_t)a * LB + b];
            cur.assign((size_t)n * m, 0);
            const vector<int> &prv = tab[(size_t)a * LB + b - 1];
            int half = 1 << (b - 1);
            int span = 1 << b;
            for (int i = 0; i < n; i++) {
                const int *p0 = &prv[(size_t)i * m];
                int *pc = &cur[(size_t)i * m];
                for (int j = 0; j + span <= m; j++)
                    pc[j] = p0[j] > p0[j + half] ? p0[j] : p0[j + half];
            }
        }
    }

    // 逐问回答
    for (int q = 0; q < K; q++) {
        int x1 = readInt() - 1, y1 = readInt() - 1;
        int x2 = readInt() - 1, y2 = readInt() - 1;
        int lx = x2 - x1 + 1, ly = y2 - y1 + 1;
        int a = lg2[lx], b = lg2[ly];
        int rx = x2 - (1 << a) + 1;   // 下方方块的起始行(绝对行号,0 起)
        int dc = ly - (1 << b);       // 右方方块相对左上角方块的列偏移
        const vector<int> &t = tab[(size_t)a * LB + b];
        const int *r0 = &t[(size_t)x1 * m];
        const int *r1 = &t[(size_t)rx * m];
        int v = r0[y1];
        if (r0[y1 + dc] > v) v = r0[y1 + dc];
        if (r1[y1] > v) v = r1[y1];
        if (r1[y1 + dc] > v) v = r1[y1 + dc];
        wInt(v);
    }
    if (opos > 0) fwrite(obuf, 1, opos, stdout);
    return 0;
}

复杂度

设 L=⌊log⁡2max⁡(n,m)⌋+1⩽9L = \lfloor \log_2 \max(n, m) \rfloor + 1 \leqslant 9。

  • 预处理:行方向 O(nmlog⁡n)O(n m \log n),列方向 O(nmlog⁡nlog⁡m)O(n m \log n \log m),合计 O(nmlog⁡nlog⁡m)≈5×106O(n m \log n \log m) \approx 5 \times 10^6 次取 max。
  • 单次询问:O(1)O(1),四次查表加三次比较。
  • 总时间:O(nmlog⁡nlog⁡m+K)O(n m \log n \log m + K);空间:O(nmlog⁡nlog⁡m)O(n m \log n \log m), 即 9×9×250×2509 \times 9 \times 250 \times 250 个 int,约 20 MB20\ \mathrm{MB}。

对照 n=m=250n = m = 250、K=106K = 10^6 的满档数据:预处理 5×1065 \times 10^6 次运算, 询问 106×O(1)10^6 \times O(1),对 22 秒的时限非常宽裕。

总结

这道题是稀疏表从一维推广到二维的标准范例,关键只有一句话: “O(1)O(1) 区间查询靠的是允许重叠的两块覆盖,二维就是把行、列各覆盖一次, 于是变成四块”。记住这一点,就不必去死记二维 ST 表的四象限递推式。

两个容易被忽略的细节:

  1. 覆盖块的起点不是 (x1,y1)(x_1, y_1) 和 (x2,y2)(x_2, y_2),而是 (x1,y1)(x_1, y_1)、(x1,y2−2b+1)(x_1, y_2 - 2^b + 1)、(x2−2a+1,y1)(x_2 - 2^a + 1, y_1)、(x2−2a+1,y2−2b+1)(x_2 - 2^a + 1, y_2 - 2^b + 1)。 写代码时把偏移量 dr=Lx−2adr = L_x - 2^a、dc=Ly−2bdc = L_y - 2^b 单独算出来会清楚很多。
  2. aa 和 bb 必须独立取。LxL_x 与 LyL_y 的 log⁡\log 值一般不同, 用一个 k 同时管两个方向是经典错误。

同一套思想还能顺势解决二维区间 gcd、二维区间按位与/或(都是可重复合并的 "幂等半群"运算),换成区间和就不行了——因为重叠部分会被重复计算。

::: tip 数据说明 本题目面来自信息学奥赛一本通·高手训练篇,但仓库内的测试数据是自造的 (素材目录带 data.py 生成脚本,按题面范围分层构造了 1×11 \times 1、单行、单列、 小网格枚举全子矩形、以及 250×250250 \times 250 满档等 1010 组点)。 素材目录里的 std.cpp 用的也是二维 ST 表,已编译并与全部 1010 组 .out 逐点比对通过, 与本文解法一致,未发现题目与标程不符的情况。 因此本地数据全部通过只说明实现自洽,不等价于官方原题 AC。 :::