对矩阵做二维稀疏表:先按行合并再按列合并,每次询问用四个 2^a×2^b 方块 O(1) 完全覆盖矩形取最大值。
OJ: roj
题目 ID: 1746
难度:提高
标签:数据结构RMQ稀疏表二维python
创建: 2026-10-07 21:06
更新: 2026-10-07 21:06
形式化题目
给定一个
数据范围:
| 档位 | ||
|---|---|---|
注意询问矩形的高度
正解
思路
朴素做法为什么不行。 最直接的想法是每次询问都双重循环扫矩形,
最坏情况下单个矩形就有
从一维 RMQ 说起。 一维的"区间最大值"是稀疏表(ST 表)的模板:
预处理 st[k][i] = max(A[i..i+2^k-1]),递推式
预处理
覆盖引理. 设
,取 ,则区间 被两个长度都是 的区间 与 完全覆盖,即它们的并集恰好等于整个区间。
证明只需注意
推广到二维。 把行方向与列方向各用一次覆盖引理,矩形就被四个方块盖住。
设
则高度为
它们同样允许重叠,并集覆盖整个询问矩形,所以取 max 是安全的。
预处理怎么递推。 直接对二维写四象限递推当然可以,但更省事、也更省常数的做法是 把两个方向拆开:
- 行方向合并。记
rowst[a][i][j]表示从第行起共 行、只取第 列这一竖条的最大值:
- 列方向合并。在固定的
层上再对列做一次同样的合并,得到真正的方块表:
这样每次合并都是"两个等长数组逐位取 max",实现上就是两次切片 + map(max, ...),
比四象限版本少一半常数。需要留意的是有效下标的范围:
rowst[a] 只有 blk[a][b] 只有
关于值域。 int,因此 C++ 侧全程用 int 即可,不需要 long long;Python 侧更是无所谓。
代码
Python 版本与 C++ 版本算法完全一致:同样是 map(max, ...) 的整行/整列操作。
#!/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++ 版本带快速读入与快速输出((a, b) 分块存放,保证一次询问的四次查表都落在同一块连续内存里。
// 一本通 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;
}复杂度
设
- 预处理:行方向
,列方向 ,合计 次取 max。 - 单次询问:
,四次查表加三次比较。 - 总时间:
;空间: , 即 个 int,约。
对照
总结
这道题是稀疏表从一维推广到二维的标准范例,关键只有一句话:
“
两个容易被忽略的细节:
- 覆盖块的起点不是
和 ,而是 、 、 、 。 写代码时把偏移量 、 单独算出来会清楚很多。 和 必须独立取。 与 的 值一般不同, 用一个 k同时管两个方向是经典错误。
同一套思想还能顺势解决二维区间 gcd、二维区间按位与/或(都是可重复合并的 "幂等半群"运算),换成区间和就不行了——因为重叠部分会被重复计算。
::: tip 数据说明
本题目面来自信息学奥赛一本通·高手训练篇,但仓库内的测试数据是自造的
(素材目录带 data.py 生成脚本,按题面范围分层构造了 std.cpp 用的也是二维 ST 表,已编译并与全部 .out 逐点比对通过,
与本文解法一致,未发现题目与标程不符的情况。
因此本地数据全部通过只说明实现自洽,不等价于官方原题 AC。
:::