【前缀和模板】：子矩阵的和（前缀和）——题解

  👋 欢迎阅读

🎯 欢迎来到「二维前缀和（子矩阵的和）」题解之旅！ 本文将带你从"快速回答矩阵任意矩形区域的和"这一直观场景出发，深入理解二维前缀和 + 容斥原理的巧妙运用，并掌握如何用四个前缀和相加减来在 O(1) 时间内回答子矩阵查询。

在开始之前，建议你先：

• 了解题目背景：这是经典的二维前缀和模板题，给定 n×m 矩阵和 q 次询问，每次询问子矩阵 (x1,y1) 到 (x2,y2) 的元素之和。本质上，子矩阵和 = 四个前缀和的容斥组合，问题转化为预处理一次、查询四次相加减。

• 明确学习目标：掌握二维前缀和的容斥构建，理解 dp[x2][y2] – dp[x1-1][y2] – dp[x2][y1-1] + dp[x1-1][y1-1] 的四项来源，并熟练处理下标从 1 开始与累加和防溢出等边界情况。

• 准备好环境：建议在本地 IDE 中打开代码，边看边运行，亲手验证示例（如 3×3 矩阵 1 2 3 / 4 5 6 / 7 8 9，查询 [1,1]-[2,2] 输出 12）。

本文将从问题转化、容斥构建、四次相减、边界防护到代码实现，层层递进。即使你对二维前缀和还不熟悉，我们也会从"大矩形减掉多余的行列，再加回重复减掉的部分"这一直觉出发，让你轻松抓住核心思想——容斥构建，四项相减。现在，让我们一起预处理二维前缀和，O(1) 回答每一次子矩阵查询吧！ 📐⚡

🏠个人主页：愿旖旎 📘专栏传送门：算法专栏 💻当前学习内容：前缀和

一.题目

【模板】前缀和_牛客题霸_牛客网

​

二、算法分析

一、问题分析（前置分析）

• 题目要求：给定 n×m 矩阵与 q 次询问，每次输出子矩阵 (x1,y1)-(x2,y2) 的元素之和。
• 关键约束：n、m、q 可能很大（可达 1e3 甚至 1e6）；元素累加和可能超出 int。
• 核心思路：暴力做法每次查询都要遍历整个子矩阵累加，总代价 O(q·n·m) 无法接受；二维前缀和一次性预处理"左上角到 (i,j) 的矩形和"，之后子矩阵和 = 四个前缀和的容斥组合，每次查询 O(1)。

📌 例子：暴力为什么不可行

矩阵 1 2 3 / 4 5 6 / 7 8 9，一次查询 [1,1]-[3,3] 需要累加 9 个数；q 次查询每次都重新遍历，最坏 O(q·n·m)。若查询的矩形越大、次数越多，重复遍历的浪费越明显——没有复用任何已算过的结果。

二、算法策略（二维前缀和 · 容斥构建 + 四次相减）

核心步骤：

📊 示例（3×3 矩阵 v，第 0 行/列全为 0）：

构建 dp（每个格子 = 左 + 上 – 左上角 + 自己）：

查询 [1,1]-[2,2]：dp[2][2] – dp[0][2] – dp[2][0] + dp[0][0] = 12 – 0 – 0 + 0 = 12（= 1+2+4+5）

三、正确性说明（简单版本）

• 构建公式自洽：dp[i][j] 表示从 (1,1) 到 (i,j) 的矩形和。dp[i][j-1] + dp[i-1][j] 覆盖了左块与上块，但左上角块被加了两次，减去 dp[i-1][j-1] 补回，再加自身 v[i][j]——容斥保证不重不漏。
• 查询公式正确：(x1,y1)-(x2,y2) = 大块 dp[x2][y2] 减去左侧多出的竖条 dp[x1-1][y2] 与上方多出的横条 dp[x2][y1-1]，但左上角块被减了两次，需加回 dp[x1-1][y1-1]——四项组合恰好留下目标子矩阵。
• 下标从 1 起步安全：x1-1、y1-1 最小为 0，dp[0][*]、dp[*][0] 恒为 0，无需特判，所有合法查询统一适用，不漏不错。

📌 例子：容斥为什么成立（以构建 dp[2][2] 为例）

dp[2][2] = dp[2][1] + dp[1][2] – dp[1][1] + v[2][2] = (1+4) + (1+2) – (1) + 5 = 12——左块 {1,4} 加上块 {1,2} 时，角上 1 被加了两次，减去一次补回，再加自己 5，恰好是 {1,2,4,5} 的和，不重不漏。

四、实现细节（边界防护）

• 初始化：v、dp 均开 (n+1)×(m+1)，第 0 行/列默认 0。
• 边界防护：下标从 1 开始避免 x1-1、y1-1 越界（dp[0][*] = 0 兜底）；累加和用 long long（1e3×1e3 个 1e9 相加达 1e15，远超 int 上限 2.1e9）；注意 Windows 下 long 是 32 位，跨平台应统一用 long long；大量查询时关闭流同步提升 IO 速度。
• 复杂度：时间 O(n×m + q)（预处理 O(n×m)，每次查询 O(1)），空间 O(n×m)（两个矩阵）。
• 关键操作：dp[i][j] = dp[i][j-1] + dp[i-1][j] – dp[i-1][j-1] + v[i][j]（构建）、dp[x2][y2] – dp[x1-1][y2] – dp[x2][y1-1] + dp[x1-1][y1-1]（查询）。

五、返回值（目标映射）

• 每次查询输出四项容斥公式的结果：子矩阵 (x1,y1)-(x2,y2) 的元素之和，对应题目"输出每次询问的子矩阵和"。

三.代码

#include <iostream>
#include <vector>
using namespace std;

int main()
{
ios::sync_with_stdio(false); // 关闭流同步，加速 IO
cin.tie(0);

int n, m, q; // n 行 m 列矩阵，q 次询问
cin >> n >> m >> q;

// 原矩阵：下标从 1 开始，第 0 行/列闲置（保持公式统一）
vector<vector<long long>> v(n + 1, vector<long long>(m + 1));
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
cin >> v[i][j];
}
}

// 1. 预处理二维前缀和：dp[i][j] = 从 (1,1) 到 (i,j) 的矩形和
vector<vector<long long>> dp(n + 1, vector<long long>(m + 1));
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
// 容斥：左块 + 上块 – 重叠角 + 自身
dp[i][j] = dp[i][j – 1] + dp[i – 1][j] – dp[i – 1][j – 1] + v[i][j];
}
}

// 2. 子矩阵查询：O(1) 四次相加减
int x1, y1, x2, y2; // 子矩阵两个角坐标
for (int i = 0; i < q; i++)
{
cin >> x1 >> y1 >> x2 >> y2;
// 大块 – 左侧竖条 – 上方横条 + 左上角块（被减两次需加回）
cout << dp[x2][y2] – dp[x1 – 1][y2] – dp[x2][y1 – 1] + dp[x1 – 1][y1 – 1] << '\\n';
}
return 0;
}

四、易错点分析

难点1：构建公式的四项来源（容斥）

dp[i][j] = dp[i][j – 1] + dp[i – 1][j] – dp[i – 1][j – 1] + v[i][j];

dp[i][j-1] 覆盖左边块，dp[i-1][j] 覆盖上边块，但左上角的 dp[i-1][j-1] 被两块同时包含、加了两次，必须减去一次；再加上自身 v[i][j]。漏掉 – dp[i-1][j-1] 或 + v[i][j] 都会让前缀和整体错位，且错误会逐格累积，最终查询全部出错。

难点2：查询公式与构建公式的容斥方向相反

dp[x2][y2] – dp[x1 – 1][y2] – dp[x2][y1 – 1] + dp[x1 – 1][y1 – 1]

构建是"左 + 上 – 重叠 + 自身"（合并），查询是"大块 – 左条 – 上条 + 重叠角"（剥离）。四个下标极易写混：dp[x2][y2] 是大块右下角，两个减项分别用 x1-1、y1-1 与 x2 交叉，加项是 (x1-1, y1-1)。建议按"右下 – 左界 – 上界 + 左上角"记忆，并逐项核对下标。

难点3：为什么减两次的角要加回来

+ dp[x1 – 1][y1 – 1] // 这个"+"的来源

大块减去左竖条 dp[x1-1][y2] 时，把左上角块 dp[x1-1][y1-1] 也减了一次；再减上横条 dp[x2][y1-1] 时，同一个角块被减了第二次。它本不属于目标子矩阵，应只被减一次，所以必须加回一次（容斥的"加回重叠"）。漏掉这个 + 会少加一个角块，仅当 x1>1 && y1>1 时错误才暴露，极难排查。

难点4：下标从 1 开始与第 0 行/列的兜底

vector<vector<long long>> dp(n + 1, vector<long long>(m + 1));
// 查询时 dp[x1 – 1][y1 – 1]，x1=1 时访问 dp[0][0]

若从 0 开始存，查询 x1=1 时 dp[x1-1] 即 dp[-1]，越界访问。从 1 开始后第 0 行/列天然为 0，x1-1=0 时公式自动退化（dp[0][y2] = 0），无需任何特判——这是"多开一圈"的经典手法。

五、流程图

 🎯 闭幕

🎉 恭喜你完成了「二维前缀和（子矩阵查询）」问题的学习！

为了巩固知识并进一步拓展，建议你：

🚀 动手实践 在 LeetCode 上提交代码，尝试不同的测试用例。

💡 深入思考

• 本题通过预处理 二维前缀和 dp[i][j]，将子矩阵查询从 O(n*m) 降至 O(1)。请问 dp[i][j] 的定义是什么？递推公式 dp[i][j] = dp[i][j-1] + dp[i-1][j] – dp[i-1][j-1] + v[i][j] 中的“容斥”思想是如何体现的？

• 查询子矩阵 (x1,y1) 到 (x2,y2) 的和用公式 dp[x2][y2] – dp[x1-1][y2] – dp[x2][y1-1] + dp[x1-1][y1-1]。为什么需要加回 dp[x1-1][y1-1]？ 请从几何覆盖角度解释。

如果你觉得本文对你有所帮助，欢迎：

👍 点赞 / 收藏 👤 关注作者，获取更多题解 💬 留言交流你的疑问或优化思路

📌 深入思考答案

• dp[i][j] 表示从 (1,1) 到 (i,j) 的 矩形内所有元素之和。递推式通过“左块 + 上块 – 左上角重叠块 + 当前元素”来计算，其中减掉重叠部分（dp[i-1][j-1]）是因为它被左块和上块重复计算了一次，这正是容斥原理的核心。

• 查询公式中 + dp[x1-1][y1-1] 是因为前两次减法（减左列和减上行）把 左上角那块小矩形 减了两次，需要加回一次以恢复真实值，这也是容斥的体现。