1. 从一道二维前缀和题说起激光炸弹到底在考什么第一次看到“激光炸弹”这个标题很多人会以为这是一道模拟爆炸效果的题甚至有人往搜索或者图论方向去想。实际上这道题的核心考点非常明确——二维前缀和。它属于那种“看起来像几何题本质是数组预处理”的典型代表。题目大意是在一个二维平面上分布着若干目标点每个点有一个价值你有一枚边长为 R 的正方形炸弹可以放在任意位置问最多能覆盖多少总价值。这道题之所以经典是因为它把二维前缀和这个知识点包装成了一个有实际场景的问题。你不需要真的去模拟爆炸也不需要处理复杂的几何关系只需要把二维网格上的数值用前缀和预处理一下然后枚举所有可能的正方形位置取最大值即可。听起来简单但真正动手写的时候坑并不少。我第一次做这道题的时候犯了一个很典型的错误把网格大小直接开成了目标点坐标的最大值结果在计算前缀和时越界了。后来才意识到炸弹的覆盖范围可能超出所有点的坐标范围所以网格的边界需要额外扩展。这个细节在题目描述里往往一笔带过但实际编码时如果忽略就会导致结果偏小甚至数组越界。这篇文章适合两类人一类是刚接触二维前缀和、想通过一道完整题目来巩固理解的新手另一类是做过了但总觉得有些细节没吃透、想看看别人踩过哪些坑的进阶选手。我会从题目本质、前缀和原理、坐标处理、边界扩展、枚举策略、常见错误这几个角度把这道题彻底拆开讲清楚。你不需要有很强的算法竞赛背景只要会基本的数组操作和循环就能跟上。2. 二维前缀和为什么能解决“正方形覆盖”问题2.1 从一维前缀和到二维的思维跃迁一维前缀和的核心思想是用sum[i]表示前 i 个元素的和这样任意区间[l, r]的和就可以用sum[r] - sum[l-1]在 O(1) 时间内算出来。这个思想搬到二维就变成了用sum[i][j]表示从(1,1)到(i,j)这个矩形区域内所有元素的和。有了这个预处理任意子矩形的和都可以用四个角的前缀和值通过容斥原理算出来。具体来说如果你想知道以(x1, y1)为左上角、(x2, y2)为右下角的矩形内所有元素之和公式是sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] sum[x1-1][y1-1]这个公式的推导其实很直观你先取整个大矩形减去上方多出来的部分再减去左方多出来的部分但左上角被减了两次所以要加回来。这就是容斥原理在二维上的体现。2.2 为什么正方形覆盖可以转化为前缀和查询激光炸弹的覆盖区域是一个边长为 R 的正方形。假设这个正方形的右下角落在(i, j)那么它的左上角就是(i-R1, j-R1)。这个正方形覆盖的总价值正好就是上面那个子矩形求和公式能直接算出来的东西。所以问题就变成了枚举所有可能的右下角位置(i, j)计算对应的正方形内价值和取最大值。这里有一个关键点正方形的边长 R 是固定的所以每个位置的计算都是 O(1) 的。总时间复杂度取决于你枚举的范围大小。如果网格是 N×N 的那总复杂度就是 O(N²)。对于这道题的数据规模来说完全够用。2.3 前缀和预处理的具体构建过程构建二维前缀和的过程也不复杂。假设原始网格是a[i][j]前缀和数组是s[i][j]那么s[i][j] s[i-1][j] s[i][j-1] - s[i-1][j-1] a[i][j]这个公式的含义是当前位置的前缀和等于上方前缀和加上左方前缀和减去左上角重复计算的部分再加上当前格子的值。你可以把它理解成“把上面和左边的信息合并起来再补上自己”。在实际编码时我习惯从下标 1 开始存数据这样就不用处理i-1或j-1为负数的情况。虽然会多开一点空间但代码会干净很多也不容易出错。提示如果你的原始数据是从下标 0 开始的建议在预处理时整体右移一位把所有坐标映射到从 1 开始。这个习惯能帮你避开大量边界判断。3. 坐标范围与网格边界的那些坑3.1 为什么不能直接用最大坐标作为网格大小很多人第一反应是读入所有点找到最大的 x 和最大的 y然后开一个maxX × maxY的数组。这个思路本身没错但问题在于炸弹的覆盖范围可能超出所有点的坐标范围。举个例子如果所有点都集中在(1,1)附近而 R 很大那么把炸弹放在(R, R)位置可能覆盖到更多点但这个位置已经超出了你开的数组范围。所以正确的做法是网格大小至少要开到maxX R和maxY R或者干脆开一个足够大的固定大小数组。很多题解会直接开 5000×5000 或者 5001×5001因为题目通常会给坐标范围一个上限。如果你不确定就去看题目里的数据范围说明然后在此基础上加上 R 的余量。3.2 坐标偏移与下标从 1 开始的实践我在实际写的时候习惯把所有坐标都加 1这样原始坐标(0,0)就变成了(1,1)。这样做的好处是前缀和数组不需要额外处理边界所有i-1和j-1都是合法下标。虽然会浪费一行一列的空间但换来的代码简洁性是值得的。具体操作是读入一个点(x, y)时直接把它存到a[x1][y1]。如果多个点落在同一个格子上就把它们的值累加。这一点也很重要因为题目可能给出重复坐标的点你需要把它们合并。3.3 炸弹边长大于网格时的处理如果 R 比整个网格还大那么炸弹可以覆盖所有点。这种情况下你不需要特殊处理只要保证网格大小足够枚举时取整个网格的和即可。但如果你开的网格太小就会漏掉一些点。所以再次强调网格大小要留足余量。另外如果 R 等于 1那问题就退化成找单个格子的最大值。这种情况下前缀和依然适用但你要确保枚举时不会越界。4. 枚举策略与最大值维护的细节4.1 枚举右下角还是左上角枚举的时候你可以选择枚举正方形的右下角也可以枚举左上角。我个人习惯枚举右下角因为这样左上角的坐标就是(i-R1, j-R1)只要保证i R且j R就行。如果你枚举左上角右下角就是(iR-1, jR-1)需要保证不超出网格边界。两种方式都可以关键是保持一致不要混用。枚举的范围通常是R到maxX RR到maxY R。这样能覆盖所有可能的位置包括那些部分超出原始点范围但仍在网格内的位置。4.2 用容斥公式计算正方形内价值和对于每个枚举到的右下角(i, j)正方形内的价值和就是s[i][j] - s[i-R][j] - s[i][j-R] s[i-R][j-R]这个公式和前面子矩形求和的公式是一样的只是左上角变成了(i-R1, j-R1)所以减去的部分是s[i-R][j]和s[i][j-R]加回来的是s[i-R][j-R]。你可以自己画个图验证一下确保下标没有差一。4.3 最大值初始化的注意事项最大值初始化的时候不要想当然地设为 0。如果所有点的价值都是负数虽然这道题通常不会那最大值可能是负数。更稳妥的做法是初始化为一个很小的数或者直接初始化为第一个枚举到的值。不过对于这道题来说价值通常是非负的所以初始化为 0 也没问题。但养成好习惯总是好的。另外如果网格中没有点那最大值就是 0。这一点在代码里自然成立不需要特殊处理。5. 代码实现与逐行注释5.1 完整代码框架下面是我自己写的一份实现用 C 写的但思路对任何语言都通用#include bits/stdc.h using namespace std; const int MAXN 5005; int s[MAXN][MAXN]; int main() { int n, r; cin n r; int maxX 0, maxY 0; for (int i 0; i n; i) { int x, y, v; cin x y v; x; y; // 坐标偏移从1开始 s[x][y] v; maxX max(maxX, x); maxY max(maxY, y); } // 构建二维前缀和 for (int i 1; i maxX r; i) { for (int j 1; j maxY r; j) { s[i][j] s[i-1][j] s[i][j-1] - s[i-1][j-1]; } } int ans 0; // 枚举右下角 for (int i r; i maxX r; i) { for (int j r; j maxY r; j) { int cur s[i][j] - s[i-r][j] - s[i][j-r] s[i-r][j-r]; ans max(ans, cur); } } cout ans endl; return 0; }5.2 关键步骤拆解这段代码有几个关键点值得展开说。第一坐标偏移是在读入时直接做的这样后面的前缀和构建和枚举都不需要再关心原始坐标。第二前缀和的构建范围是maxX r和maxY r这是为了确保炸弹可以放在所有可能的位置。第三枚举时从r开始因为右下角至少要在(r, r)才能保证左上角不小于(1,1)。如果你用的是 Python思路完全一样只是要注意二维数组的创建方式和循环效率。Python 的列表推导式可以帮你快速初始化二维数组但嵌套循环可能会慢一些。对于这道题的数据规模Python 通常也能过但如果超时可以考虑用 NumPy 或者优化循环。5.3 空间与时间的权衡开一个 5005×5005 的 int 数组大约占用 100MB 左右的内存。如果内存限制比较紧你可以根据实际的最大坐标来动态开数组或者用 vector 来管理。但大多数情况下直接开固定大小是最省事的。时间上预处理和枚举都是 O(N²)对于 N5000 来说大约 2500 万次操作C 完全能在 1 秒内跑完。Python 可能需要几秒但通常也在可接受范围内。6. 那些年我踩过的坑与调试经验6.1 数组越界与下标差一最常见的错误就是数组越界。比如你在构建前缀和时循环到了maxX r但数组只开到了maxX那就会越界。或者你在枚举时用了i-r但i从 0 开始导致负数下标。这些错误在本地可能不会崩溃但结果会莫名其妙地不对。我的建议是在写循环边界时先在纸上画一个简单的例子比如 3×3 的网格R2手动算一遍确认下标范围。然后再写代码这样能避免大部分差一错误。6.2 重复点合并的遗漏题目可能给出多个相同坐标的点如果你直接覆盖而不是累加就会丢失价值。我在第一次写的时候用了s[x][y] v而不是s[x][y] v结果答案偏小。后来改成累加就对了。这个坑很隐蔽因为如果测试数据没有重复点你根本发现不了。6.3 最大值初始化为 0 的隐患虽然这道题的价值通常是非负的但如果你把最大值初始化为 0而所有可能的覆盖价值都是负数比如点都是负价值那答案就会错。更稳妥的做法是初始化为INT_MIN或者第一个枚举值。不过对于这道题初始化为 0 通常没问题但知道这个隐患的存在能让你在遇到类似问题时更快定位。6.4 网格大小不足导致的漏解前面已经强调过网格大小要开到maxX r和maxY r。如果你只开到maxX和maxY那炸弹放在边缘时就会漏掉一些点。这个错误在调试时很难发现因为你的代码逻辑看起来是对的只是结果偏小。解决方法是在枚举时打印一下你实际枚举的范围看看是否覆盖了所有可能的位置。7. 从这道题延伸出的二维前缀和实战技巧7.1 二维前缀和的通用模板掌握了这道题之后你可以把二维前缀和当成一个通用工具。它的标准模板是预处理s[i][j] s[i-1][j] s[i][j-1] - s[i-1][j-1] a[i][j]查询sum(x1,y1,x2,y2) s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] s[x1-1][y1-1]只要涉及到“子矩阵求和”或者“固定形状区域求和”的问题都可以往这个方向想。7.2 什么时候不该用二维前缀和二维前缀和适合静态数据、多次查询的场景。如果数据会动态更新那前缀和就不适用了需要考虑树状数组或者线段树。另外如果查询的区域不是矩形而是圆形或者不规则形状前缀和也无能为力。所以用之前先确认问题的性质。7.3 类似题目的解题思路迁移很多题目都是二维前缀和的变种。比如“最大子矩阵和”可以用前缀和加枚举“统计全为1的正方形子矩阵”可以用动态规划加前缀和。你只要抓住“预处理O(1)查询”这个核心就能把这道题的经验迁移到其他问题上。我在实际练习中会把这类题目归类到一个专题里每道题都写一份题解记录自己的思路和踩过的坑。这样过一段时间再回头看能快速回忆起关键点也能看到自己的进步。对于激光炸弹这道题我的题解里特别标注了“坐标偏移”和“网格扩展”这两个细节因为它们是这道题最容易出错的地方。最后分享一个小技巧如果你在比赛中遇到类似的二维网格题不确定网格该开多大就直接开一个比题目数据范围上限大 100 的数组。多开一点空间不会影响正确性但能帮你避免越界。这个习惯我用了很多年救了我很多次。