欢迎阅读 欢迎来到「二维前缀和子矩阵的和」题解之旅本文将带你从快速回答矩阵任意矩形区域的和这一直观场景出发深入理解二维前缀和 容斥原理的巧妙运用并掌握如何用四个前缀和相加减来在 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)。若查询的矩形越大、次数越多重复遍历的浪费越明显——没有复用任何已算过的结果。二、算法策略二维前缀和 · 容斥构建 四次相减核心步骤读入矩阵v[1..n][1..m]存原始数据下标从 1 开始第 0 行/列闲置。预处理二维前缀和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]大块 - 左条 - 上条 重叠角。循环输出处理 q 次询问每次 O(1) 四次相加减。 示例3×3矩阵v第 0 行/列全为 0i\j012300000101232045630789构建 dp每个格子 左 上 - 左上角 自己i\j01230000010136205122130122745查询[1,1]-[2,2]dp[2][2] - dp[0][2] - dp[2][0] dp[0][0] 12 - 0 - 0 0 121245三、正确性说明简单版本构建公式自洽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最小为 0dp[0][*]、dp[*][0]恒为 0无需特判所有合法查询统一适用不漏不错。 例子容斥为什么成立以构建 dp[2][2] 为例dp[2][2] dp[2][1] dp[1][2] - dp[1][1] v[2][2] (14) (12) - (1) 5 12——左块{1,4}加上块{1,2}时角上1被加了两次减去一次补回再加自己5恰好是{1,2,4,5}的和不重不漏。四、实现细节边界防护初始化v、dp均开(n1)×(m1)第 0 行/列默认 0。边界防护下标从 1 开始避免x1-1、y1-1越界dp[0][*] 0兜底累加和用long long1e3×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 行/列闲置保持公式统一 vectorvectorlong long v(n 1, vectorlong 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) 的矩形和 vectorvectorlong long dp(n 1, vectorlong 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]时同一个角块被减了第二次。它本不属于目标子矩阵应只被减一次所以必须加回一次容斥的加回重叠。漏掉这个会少加一个角块仅当x11 y11时错误才暴露极难排查。难点4下标从 1 开始与第 0 行/列的兜底vectorvectorlong long dp(n 1, vectorlong long(m 1)); // 查询时 dp[x1 - 1][y1 - 1]x11 时访问 dp[0][0]若从 0 开始存查询x11时dp[x1-1]即dp[-1]越界访问。从 1 开始后第 0 行/列天然为 0x1-10时公式自动退化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]是因为前两次减法减左列和减上行把左上角那块小矩形减了两次需要加回一次以恢复真实值这也是容斥的体现。