在 蓝桥杯软件赛（C/C++·Python 程序设计）、全国青少年信息素养大赛算法应用主题赛，以及中国电子学会软件编程（C/C++、Python）等级考试的真题里，矩阵、网格统计类题目几乎年年出现：给你一张成绩单矩阵，反复询问「某一块矩形区域的总分是多少」。如果每次询问都暴力求和，数据一大就超时；而 二维前缀和 能用一次预处理，把任意子矩阵的求和压到 O(1)。本文用一道原创题讲透它的原理、代码（C++ / Python 双版）、七个易错点和进阶变形。
锚点速览（备赛正当时）：第十八届蓝桥杯软件赛报名 2026-10-08 10:00—2026-12-18 14:00，省赛 2027-04-10（C/C++·Python 程序设计 9:00–13:00），总决赛 2027-06-12（dasai.lanqiao.cn）；中国电子学会 2026 年 12 月软件编程（C/C++ 一级至十级、Python 一级至六级）等级考试报名 9/23–12/2 16:00、统考 12-12（C/C++ 8:30–10:30、Python 14:00–15:00）；全国青少年信息素养大赛 2026—2027 赛季算法应用主题赛。
一、原创题目：校园科技节方阵得分统计
【题目描述】
校园科技节上，n 行 m 列的展位方阵中，每个展位有一个整数得分（可能为负数，表示扣分项）。赛后组委会要回答 q 次询问：每次给出子矩阵左上角 (x1, y1) 和右下角 (x2, y2)（坐标均为 1 起始、闭区间），求该矩形内所有展位得分的总和。
【输入格式】
第一行 n, m, q；接下来 n 行每行 m 个整数（展位得分）；接下来 q 行每行四个整数 x1, y1, x2, y2。
【输出格式】
对每个询问输出一行，为该子矩阵得分之和。
【数据范围】
1 ≤ n, m ≤ 1000，1 ≤ q ≤ 100000，得分 ∈ [−1000, 1000]。
【样例】
矩阵：
1 2 3
4 5 6
7 8 9
- 询问
2 2 3 3（右下 2×2：5,6 / 8,9）→ 输出 28 - 询问
1 1 3 3（整个矩阵）→ 输出 45
暴力做法对每个询问 O(n·m)，总复杂度 O(q·n·m) ≈ 10⁹，必然超时——这正是二维前缀和要解决的问题。
二、核心考点拆解
- 前缀和的本质是「容斥」：一维前缀和是「前面一段的和」；二维前缀和则是「左上角到 (i,j) 这个矩形的和」，查询时用四个角做加减抵消，得到任意子矩阵的和。
- 建表 O(n·m)：先把每个
(i,j)的「以 (1,1) 为左上、以 (i,j) 为右下的矩形和」算好，存进s[i][j]。 - 查询 O(1)：任意子矩阵和 =
s[x2][y2] − s[x1−1][y2] − s[x2][y1−1] + s[x1−1][y1−1]。 - 1 起始下标偏移技巧：矩阵用 1 起始、前缀和数组多开一行一列（
s[0][*] = s[*][0] = 0），这样x1=1时s[0][*]自然为 0，查询不用特判越界——这是写对的关键。
三、二维前缀和公式
建表递推（经典「上 + 左 − 左上的左上」）：
s[i][j] = a[i][j] + s[i-1][j] + s[i][j-1] - s[i-1][j-1]
子矩阵求和（「右下 − 上多算 − 左多算 + 重复减掉的一次」）：
sum = s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1]
四个项 「两减一加」 的顺序和符号必须严格对齐，写错一个符号结果就会变成 0 或乱值。
四、解法与代码（C++ / Python 双版）
4.1 Python 实现
def build_prefix(a, n, m):
# a 为 0 起始二维列表；返回 1 起始前缀和 s（s[0][*]=s[*][0]=0）
s = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, m + 1):
s[i][j] = a[i-1][j-1] + s[i-1][j] + s[i][j-1] - s[i-1][j-1]
return s
def rect_sum(s, x1, y1, x2, y2):
# 1 起始闭区间 [x1,x2] × [y1,y2]
return s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1]
# 样例验证
a = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
s = build_prefix(a, 3, 3)
print(rect_sum(s, 2, 2, 3, 3)) # 28
print(rect_sum(s, 1, 1, 3, 3)) # 45
4.2 C++ 实现
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// 构建二维前缀和（1 起始）
vector<vector<ll>> buildPrefix(const vector<vector<int>>& a, int n, int m) {
vector<vector<ll>> s(n + 1, vector<ll>(m + 1, 0));
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
s[i][j] = (ll)a[i-1][j-1] + s[i-1][j] + s[i][j-1] - s[i-1][j-1];
return s;
}
// O(1) 子矩阵求和
ll rectSum(const vector<vector<ll>>& s, int x1, int y1, int x2, int y2) {
return s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1];
}
int main() {
vector<vector<int>> a = {{1,2,3},{4,5,6},{7,8,9}};
int n = 3, m = 3;
auto s = buildPrefix(a, n, m);
cout << rectSum(s, 2, 2, 3, 3) << "\n"; // 28
cout << rectSum(s, 1, 1, 3, 3) << "\n"; // 45
return 0;
}
4.3 时间 / 空间复杂度
- 时间：建表 O(n·m)，每次询问 O(1)，总 O(n·m + q)。q=10⁵、n·m=10⁶ 轻松通过。
- 空间：前缀和数组 O(n·m)。注意 C++ 用
long long：满分可达 1000×1000×1000 = 10⁹，远超过int上限（约 2.1×10⁹ 看似够，但负分累加会越界），务必开long long；Python 自动大整数无此忧。
五、七个易错点（提分必看）
- 下标偏移：统一用 1 起始 + 多开一行一列，避免
x1−1当x1=1时越界；用 0 起始写查询极易在边界 WA。 - 容斥符号：四项是「右下 − 上 − 左 + 左上」，少加或多减都会算错，建议背熟再默写。
- 建表顺序：i、j 必须从小到大递推，否则依赖的前缀还没算出来。
- 坐标体系：题目给的可能是 0 起始，进场先统一
+1转成 1 起始；混用直接错。 - 矩形合法性：若题目不保证
x1≤x2，进场用swap/取min,max防御，否则下标倒挂会越界。 - 初始值误导：若题目要求「最大子矩阵和」，初值必须用
-INF而非0（矩阵可能全负），否则答案永远 ≥0。 - 整数溢出：C++ 必须用
long long存前缀和与答案；只把矩阵本身存int即可。
六、进阶：最大子矩阵和（蓝桥杯省赛经典变形）
把题目升级为：求整个矩阵中元素和最大的子矩阵（可为任意位置、任意大小）。这正是「二维前缀和 + 一维最大连续子段和（Kadane）」的经典组合。
思路：枚举上边界 top 与下边界 bottom（O(n²)），把这两行之间的每一列「压」成一维数组（列和），然后在该一维数组上跑 Kadane 求最大连续子段和，全局取最大。复杂度 O(n²·m)。
Python 实现：
def max_submatrix(a, n, m):
best = -10**18
for top in range(n):
col = [0] * m
for bottom in range(top, n):
for j in range(m):
col[j] += a[bottom][j] # 把 [top,bottom] 行压成一维
cur = 0; mx = -10**18
for v in col: # Kadane 一维最大子段和
cur = max(v, cur + v)
if cur > mx: mx = cur
if mx > best: best = mx
return best
# 样例（全正矩阵）最大即整体 45
print(max_submatrix([[1,2,3],[4,5,6],[7,8,9]], 3, 3)) # 45
C++ 实现：
ll maxSubmatrix(const vector<vector<int>>& a, int n, int m) {
ll best = -1e18;
for (int top = 0; top < n; ++top) {
vector<ll> col(m, 0);
for (int bottom = top; bottom < n; ++bottom) {
for (int j = 0; j < m; ++j) col[j] += a[bottom][j];
ll cur = 0, mx = -1e18;
for (ll v : col) { cur = max(v, cur + v); if (cur > mx) mx = cur; }
best = max(best, mx);
}
}
return best;
}
进阶延伸：① 二维差分——与二维前缀和「互逆」，用于「矩形区域整体加一个值」，同样 O(1) 修改、最后 O(n·m) 还原；② 高维前缀和——三维体积统计；③ 二维哈希——快速判断两个子矩阵是否完全相同；④ 前缀和优化 DP——很多网格 DP 的转移可用前缀和把 O(n) 降到 O(1)。
七、小结与互动
二维前缀和是「以空间换时间」思想的典范：一次 O(n·m) 预处理，换取任意子矩阵 O(1) 查询，是蓝桥杯网格题、电子学会考级数组章节、信息素养大赛算法赛项的必备工具。记住口诀「建表：上+左−左上；查询：右下−上−左+左上」，再避开上面的七个坑，这一类题就能稳定拿分。
互动：你在刷题时遇到过哪些二维前缀和相关的「坑」或好题？欢迎在评论区留言，下一篇我们可以聊聊它的孪生兄弟——二维差分与矩形区间修改。
📚 免费少儿编程资料（夸克网盘领取）
以下资料来自夸克网盘分享，点击链接可直接保存；若需在 App 内打开，也可复制下方明文链接：
- 全国青少年信息素养大赛复赛集训题目Python&C++.docx
https://pan.quark.cn/s/93995d3cb150 - 2024信息素养-智能算法应用挑战赛-复赛初中组题目7月7日.pdf
https://pan.quark.cn/s/da97b5dbf75d - Python背记手册.pdf
https://pan.quark.cn/s/7568ae9ca92b - Python课程
https://pan.quark.cn/s/a94bf02d00c6 - 2024信息素养大赛图形化复赛集训题答案3-9
https://pan.quark.cn/s/6ccab7ec3cbc - 2025年03月份电子学会考级真题
https://pan.quark.cn/s/4403c4228912 - 2025全国青少年信息素养大赛赛项说明
https://pan.quark.cn/s/d9d0df4a9f29 - 青少儿信息素养大赛编程资料
https://pan.quark.cn/s/4ab6bd83be8a
资料持续更新，关注获取最新分享。
转载自 CSDN-专业IT技术社区
原文链接：https://blog.csdn.net/IT_Scratch/article/details/170755141
