前缀和与矩阵区域和：从一维到二维，8个高频变体全解析

我面试的时候经常让候选人写一道题给一个二维矩阵要求快速回答任意子矩阵的元素和。第一次答暴力遍历我还能接受但等我追问一句“query 有一万次矩阵 1000×1000你还暴力吗”很多人就开始卡壳了。这时候前缀和就该登场。这篇聊的核心就是前缀和思想以及它在“矩阵区域和”这一类题型里的完整应用。标题里的“(8)”我按最常见的8个高频考核场景来拆解。你会看到一维前缀和怎么平滑升级成二维前缀和、那个经典的容斥公式是怎么推导出来的、8种矩阵区域和的变体分别怎么破以及我踩过的那些边界和溢出的坑。适合算法刚入门、准备面试、或者刷 LeetCode 时被二维区域和卡住的朋友看完可以直接上手。1. 前缀和的本质把查询 O(n) 砍成 O(1)1.1 先从一维看起区间和为什么需要预处理一维前缀和几乎所有刷题的人都写过但很多人只背了公式没理解它解决的本质问题。假设有一个数组nums长度 n你要回答 m 次“从下标 l 到下标 r 的元素和”。最直接的做法是每次循环累加单次查询 O(n)m 次就是 O(mn)。当 n 和 m 都到 10^5 级别计算量是 10^10基本跑不动。前缀和的思路是既然区间和是“从 0 到 r 的和”减去“从 0 到 l-1 的和”那我干脆提前把“从 0 到每个位置的和”都算好存到一个数组里。以后每次查询直接拿两个预存值相减O(1) 出结果。具体的构建方式是int n nums.length; long[] pre new long[n 1]; for (int i 1; i n; i) { pre[i] pre[i - 1] nums[i - 1]; } // 查询 [l, r]入参是 0-based 下标 long sum pre[r 1] - pre[l];这里有一个新手很容易忽略的设计前缀和数组的长度是 n1pre[0]固定为 0。好处是当 l0 时pre[l]就是pre[0]0不需要特判同时所有“减一”的操作都在构建时处理好了查询公式统一不容易出错。我个人的习惯是前缀和数组用long而不是int。原因后面会专门说先记住区间和数据量大时很容易超过 int 上限用 long 能省掉一大半隐蔽的溢出错。1.2 前缀和解决数据依赖构建过程是串行链但查询零依赖“前缀和解决数据依赖”这个说法听起来玄乎其实指的是两件事。第一件事是查询阶段的数据依赖。没有前缀和时区间和依赖区间里所有元素的值每次都要重新遍历有了前缀和查询结果只依赖pre[r]和pre[l-1]两个预计算结果原始数组的依赖被彻底解耦了。这是前缀和能力最强的点一次预处理N 次 O(1) 查询典型的空间换时间预处理 O(n)查询 O(1)总复杂度从 O(mn) 降到 O(nm)。第二件事是构建阶段的依赖关系。pre[i]依赖pre[i-1]这是严格的数据依赖链。小数据量下无所谓几百万个元素线性扫过去也就毫秒级。但如果矩阵大到了需要分布式或 GPU 并行处理的级别这条依赖链就是瓶颈。打破依赖链的常规做法是分块预处理把数组切成若干块每个块先独立算出块内前缀和再用每个块的最后一个元素串行算出“块之间的前缀和”最后每个块内部再叠加块间前缀和得到完整结果。第一步和第三步块内可以完全并行只有第二步的块间计算是串行的数据依赖从 O(n) 的串行链降低到了 O(块数) 的串行链这就是大规模数据下“前缀和解决数据依赖”的工程意义。刷题阶段知道这层背景就够了主要在理解为什么前缀和适合“静态数据、频繁查询”而一旦数据需要频繁修改构建链会被反复打破那时就该考虑树状数组或线段树。1.3 为什么矩阵区域和需要二维前缀和把一维的区间和升级到二维就是“矩阵区域和”问题的核心需求给定 m×n 的矩阵回答任意子矩阵(row1, col1, row2, col2)的元素和。直觉上可以按行拆先对每一行做一维前缀和查询子矩阵时逐行用一维公式累加。这样单次查询 O(行数)最坏 O(m)。如果查询次数多还是不够快。二维前缀和更进一步——把“按行累加”也预处理好直接构造一个pre[i][j]表示“从 (0,0) 到 (i,j) 这个大矩形的所有元素和”。这样任意子矩阵和就能用四个大矩形的组合算出来查询降到 O(1)。这就是经典的容斥原理也是整个二维前缀和最重要的公式值得花点篇幅彻底讲透。2. 矩阵区域和核心实现容斥公式与边界处理2.1 容斥原理推导为什么是“减两个加一个”二维前缀和的核心问题有两个怎么构建pre[i][j]怎么用它算任意子矩阵和。先看构建。pre[i][j]代表从矩阵左上角 (0,0) 到 (i,j) 的全部元素和。它可以由已经算好的三块拼出来上面的矩形pre[i-1][j]、左边的矩形pre[i][j-1]两者叠加后左上角那块pre[i-1][j-1]被加了两次所以要减掉一次最后再加上当前格子的值matrix[i][j]。for (int i 1; i m; i) { for (int j 1; j n; j) { pre[i][j] pre[i-1][j] pre[i][j-1] - pre[i-1][j-1] matrix[i-1][j-1]; } }这就是“减一个”的来源。构建时减一次是为了纠正左上角被重复计算。再看查询。要求子矩阵 (r1, c1) 到 (r2, c2) 的和可以把它看成“大矩形减两块再加回多减的小块”。大矩形是pre[r2][c2]减去上边pre[r1-1][c2]减去左边pre[r2][c1-1]因为左上角那块pre[r1-1][c1-1]被减了两次所以再加回来。public int sumRegion(int r1, int c1, int r2, int c2) { return pre[r21][c21] - pre[r1][c21] - pre[r21][c1] pre[r1][c1]; }注意这里我沿用了一维时的技巧pre数组是 (m1)×(n1)下标从 1 开始。所以查询时传入的原始坐标需要各自加 1 来映射也就是把r1映射成r11的位置。这样当 r10 时pre[0][c21]永远是 0不需要特判。为了好记你可以把构建和查询都想象成“大矩形拼装”构建是“上左-左上当前”查询是“大-上-左左上”。两组公式结构一致都是容斥记住一组基本上另一组也不会错。2.2 LeetCode 304 完整解法从建类到查询LeetCode 304 号题就是经典的原题复现。题目要求你的类支持构造和查询两个操作构造一次查询多次。完整代码如下class NumMatrix { private final int[][] pre; public NumMatrix(int[][] matrix) { int m matrix.length; int n matrix[0].length; pre new int[m 1][n 1]; for (int i 1; i m; i) { for (int j 1; j n; j) { pre[i][j] pre[i-1][j] pre[i][j-1] - pre[i-1][j-1] matrix[i-1][j-1]; } } } public int sumRegion(int row1, int col1, int row2, int col2) { return pre[row21][col21] - pre[row1][col21] - pre[row21][col1] pre[row1][col1]; } }构建复杂度 O(mn)单次查询 O(1)额外空间 O(mn)。这个复杂度在绝大多数场景下是最优的——不可能比 O(1) 的查询更快因为答案根本就不依赖查询区域里的每一个元素了。有个容易被问到的细节LeetCode 304 的返回值是 int但面试时如果矩阵元素值和范围变大建议改用 long。这个习惯在真实业务场景里更重要因为很多线上问题都不是算法错了而是 int 溢出后出现莫名其妙的负数。2.3 边界条件与防溢出我踩过的三个典型坑二维前缀和的代码短坑却非常集中我列一下实际中遇到最多的三种第一个坑是matrix[0].length空指针。题目说矩阵非空时没问题但真实场景里 m 或 n 可能为 0构造时直接访问matrix[0]就崩了。稳妥做法是在构造开头加一句空矩阵判断。第二个坑是 int 溢出。LeetCode 304 的数值范围不大int 够用。但如果你处理的是图像像素累计、灰度图卷积之类的任务一个 1000×1000 的矩阵区域和轻松超过 21 亿。我建议一律用long存前缀和查询返回值也声明为 long。省不了多少内存却能避免最隐蔽的 bug。第三个坑是坐标混淆。有人喜欢把pre数组下标设计成和原矩阵完全一致也就是从 0 开始构建。不是不行但查询公式里会出现大量if (r1 0)之类的分支。我实测下来多一行1的映射复杂度远远小于处理边界分支的复杂度所以统一推荐“下标 0 空置”的写法。提示面试时哪怕你不写边界判断也务必要口头提一句“这里要考虑空矩阵/溢出”这能直接体现代码的工程素养属于性价比极高的加分动作。3. 矩阵区域和的8个高频变体从板子题到进阶题标题里的“(8)”我按矩阵区域和最常见的8个考核方向来拆。这8个方向并不是简单罗列题号而是把二维前缀和的典型应用场景和变形路径铺开从基础板子到进阶思维都有。它们未必全都直接用二维前缀和求解但核心思路都和“预计算 O(1) 查询”一脉相承。3.1 场景一求和为 K 的子矩阵数量这是 LeetCode 1074也是二维前缀和的升级题。给定矩阵求元素和等于 K 的子矩阵个数。朴素思路是枚举所有子矩阵再用二维前缀和 O(1) 求其和总复杂度 O(m²n²)数据一大必然超时。优化的关键是把二维问题压回一维。固定子矩阵的上边界 i 和下边界 j把第 i 行到第 j 行的同一列元素全部累加就得到一个长度为 n 的“列累加数组”。问题变成在这个数组里找有多少个连续子数组的和等于 K。而一维子数组求和为 K用“前缀和 哈希表”扫描一遍就能在 O(n) 内解决整体复杂度降到 O(m²n)。// 核心思路伪代码 for (int top 0; top m; top) { int[] colSum new int[n]; for (int bottom top; bottom m; bottom) { // 累加每一列形成一维数组 for (int c 0; c n; c) colSum[c] matrix[bottom][c]; // 对这个一维数组套用“前缀和 哈希”求等于K的子数组数量 } }这个变形题属于“表面考矩阵实际考一维前缀和扩展”的典型面试中出现的频率很高。关键在于你要能识别出上下边界可以枚举以及枚举后问题降维。3.2 场景二最大子矩阵和这是 LeetCode 面试题 17.24也是求最大子数组和的二维扩展。给定矩阵找出元素和最大的子矩阵。思路和场景一几乎一样枚举上下边界把多行压缩成一维数组然后在这个一维数组上跑 Kadane 算法动态规划版最大子数组和。由于 Kadane 是 O(n)加上枚举上下边界 O(m²)总复杂度 O(m²n)。如果矩阵是正方形就是 O(n³)。这个题不要求二维前缀和但它依赖“压缩一维化”的思维和前缀和的组合思路一致。要注意的是返回的不是和而是子矩阵的坐标。所以在跑 Kadane 时要同时记录一维数组里最大子段的起点和终点再结合当前枚举的上下边界推出原始矩阵中的行号和列号。这块代码比单纯求值麻烦不少面试时建议先把求值的部分讲清楚再加坐标记录。3.3 场景三区域和查询类的在线变体很多业务场景里矩阵本身不常变化但查询请求源源不断这就是“在线查询”场景。LeetCode 304 本身已经覆盖了这种需求但实际业务中可能还会叠加“多个矩阵版本”的问题。比如你有一个历史版本矩阵要回答“某版本中某区域的和”那就得把前缀和按版本存成多份。这可以演化成可持久化数据结构但多数情况下直接存多份二维前缀和就够了。面试里如果被问到“如果矩阵会更新怎么办”答案转向树状数组或线段树如果被问到“如果查询的是多个历史版本”答案转向可持久化线段树或分段存储。理解了二维前缀和的定位这些延伸你就能对答如流。3.4 场景四子矩阵平均值是否超过阈值LeetCode 1314 矩阵区域和题干要求的是把每个格子替换成它 k×k 邻域内元素和的平均值核心就是二维前缀和做窗口聚合。类似地还有一个经典问题给一个整数矩阵和一个阈值判断是否存在一个 k×k 的子矩阵其平均值大于阈值。这类题的解法模板非常固定先构建二维前缀和然后对每个可能的 k×k 窗口左上角用 O(1) 的容斥公式求出子矩阵和最后除以 k² 和阈值比较。这里有个省时间的技巧用sum threshold * k * k替代sum / (k * k) threshold。浮点除法慢且可能有精度问题整数乘法简单且无损。小到竞赛大到工程这个替换都能用。3.5 场景五差分数组 二维前缀和还原这是二维前缀和的“反向应用”。如果题目给你一个全 0 矩阵然后进行大量“将某个子矩阵区域内所有元素加一个值”的更新操作最后才需要输出最终矩阵那么差分数组才是主角。一维差分是“区间加单点查”的利器在区间起点加 val、终点后一位减 val最后前缀和还原。二维差分就是它的扩展对子矩阵 (r1, c1, r2, c2) 加 val只需要在四个角标记diff[r1][c1] val; diff[r21][c1] - val; diff[r1][c21] - val; diff[r21][c21] val;所有更新做完对 diff 做一次二维前缀和就得到最终矩阵。单次更新 O(1)最后的还原 O(mn)。如果更新次数很多而最终只需要输出一次这个方案比每次直接遍历子矩阵 O(更新次数 × 区域大小) 快几个数量级。这个场景建议和场景一对照着学一个从原始矩阵构造前缀和用于查询一个从差分矩阵用前缀和还原出结果。两者一正一反刚好把前缀和的对称性吃透。3.6 场景六子矩阵最大边长与全 1 方阵判断LeetCode 221 最大正方形和 LeetCode 85 最大矩形都不是直接用二维前缀和求解但所有题解在讲解时几乎都会提到“前缀和可以用来快速验证某个区域是否全 1或者是否全 0”。具体来说如果你用二分答案枚举可能的正方形边长 L然后判断是否存在一个 L×L 的子矩阵的元素和等于 L²全 1 情况或等于 0全 0 情况这个判断就可以用二维前缀和 O(1) 完成。于是整体复杂度从暴力 O(m²n²) 降到 O(mn log(min(m, n)))。虽然最优解通常是动态规划 单调栈但前缀和 二分的思路在面试中反而更能体现你对“验证区域性质”这一类问题的理解深度。我的建议是动态规划解法要会二分 前缀和的验证方案也要会。前者刷题必备后者在讨论复杂度、优化路径时非常加分。3.7 场景七大型矩阵的分块稀疏查询这个场景主要针对真实业务。当矩阵特别大比如 10^5 × 10^5完整的二维前缀和数组根本存不下但查询区域只覆盖少数热点区块时可以换一种组织方式按行维护一维前缀和再额外维护一个“稀疏区块索引”。查询时按行做一维区间和累加只在命中了预计算的稀疏区块时直接用区块结果跳过大量计算。这相当于把 O(行数) 的查询退化为 O(命中区块数)代价是构建和维护区块索引的复杂度。这个思路在时序数据、地理网格数据的聚合分析里很常见。面试官如果问到“矩阵太大放不下完整前缀和怎么办”能说出分块 稀疏索引这个方案会让人觉得你做过真实的大数据处理而不是只背了算法板子。3.8 场景八多哈希与高维扩展最后一个是思维扩展题如果矩阵里的元素不是数值而是字符串哈希值你可以用“二维哈希前缀”在 O(1) 内比较两个任意子矩阵是否完全相同。这个技巧在 2D 模式匹配、图像重复检测里非常实用。原理和一维字符串哈希完全一致给每个位置分配一个随机大整数作为元素哈希值然后用二维前缀和的容斥公式求出任意子矩阵的哈希和注意这里哈希运算用可逆操作而不是简单的求和常用的是移位异或或者取模加法。两个子矩阵的哈希值相同大概率就代表它们内容相同。高维扩展同理三维体数据可以做三维前缀和这时候容斥公式从 4 项变成 8 项即(1,1,1)到(i,j,k)的体积和等于pre[i-1][j][k] pre[i][j-1][k] pre[i][j][k-1] - pre[i-1][j-1][k] - pre[i-1][j][k-1] - pre[i][j-1][k-1] pre[i-1][j-1][k-1]。原则就是“奇数个减一的项加偶数个减一的项减”容斥公式的规律在高维同样适用。4. 常见问题与排查技巧实录4.1 高频错误速查表我把实际调试中遇到最多的报错和错误结果整理成一个速查表对着排查基本能定位大多数问题。症状可能原因解决方案查询结果整体偏大或出现负数int 溢出前缀和数组改用 long第一行/第一列结果错误下标映射出错pre[i-1][j]访问了原矩阵索引统一用 n1 维度原矩阵下标减一空矩阵构造时抛异常未判断 m0 或 n0构造开头加空矩阵返回矩形边界坐标越界查询时把 r2 或 c2 直接当成前缀和下标所有映射用 r21、c21差分还原结果错乱差分标记点位置错误四个角分别为 (r1, c1)、(r21, c1)、(r1, c21)、(r21, c21)哈希值冲突导致误判哈希函数设计太弱使用双哈希或随机大模数4.2 调试技巧小矩阵手算验证数