1. 从一道二维前缀和经典题说起激光炸弹这道题在算法竞赛圈子里算是二维前缀和的入门必修课。我第一次碰到它的时候还在一家小公司的算法组做数据清洗当时觉得这不就是个矩形覆盖问题吗结果真上手写才发现边界处理和空间优化全是坑。题目大意是这样的在一个二维平面上分布着若干目标点每个点有一个价值你手里有一枚正方形的炸弹边长固定为R问你怎么扔才能炸掉总价值最高的目标。听起来简单但数据范围一上来暴力枚举就彻底没戏了。这道题的核心价值在于它把二维前缀和这个工具用最直白的方式推到了你面前。你不需要会什么高级数据结构也不需要动态规划的状态转移只要能把二维前缀和数组建对、查询写对这题就能拿满分。但恰恰是“建对”和“写对”这两个词卡住了无数刚接触二维前缀和的新手。我见过太多人把前缀和数组的维度搞混或者查询的时候下标越界最后对着WA的提交记录发呆。这篇文章适合谁看如果你刚学完一维前缀和想找个题练手二维版本那这道题就是为你量身定做的。如果你已经做过几道二维前缀和的题但总是被边界条件折磨那这篇文章里的细节处理经验应该能帮你省下不少调试时间。甚至如果你只是好奇“前缀和到底能解决什么实际问题”我也会在后面的内容里用生活化的例子把它讲清楚。整篇文章我会按照思路拆解、核心细节、实操实现、问题排查四个大块来展开每一块都会配上我实际踩过的坑和总结出来的技巧。2. 二维前缀和到底在算什么2.1 从一维到二维的思维跃迁一维前缀和的概念大家应该都熟给你一个数组你预处理出一个前缀和数组然后就能在O(1)时间内求出任意区间的和。这个思路搬到二维平面上就变成了给你一个矩阵你预处理出一个二维前缀和数组然后就能在O(1)时间内求出任意子矩阵的和。听起来只是维度加了一但实际写起来下标的处理复杂度是指数级上升的。我用一个生活化的类比来解释。假设你有一张Excel表格每个单元格里有一个数字。一维前缀和就像是你把每一行的数字从左到右累加得到一个新的行。二维前缀和则是你把整个表格做一个“累积和”的操作每个位置的新值等于它左上角所有单元格原始值的总和。这样当你想知道表格中任意一个矩形区域的总和时你不需要把区域内的单元格一个个加起来而是用四个角的前缀和值做一次加减法就能得到。这个“四个角做加减法”的操作就是二维前缀和查询的精髓。具体来说如果你要求左上角在(x1, y1)、右下角在(x2, y2)的矩形区域和公式是sum pre[x2][y2] - pre[x1-1][y2] - pre[x2][y1-1] pre[x1-1][y1-1]这个公式的推导过程我建议每个初学者都在纸上画一遍。画一个3x3的格子标上数字然后手动算一遍前缀和再用公式去查一个2x2的区域看看结果对不对。我当年就是这么干的画了三遍之后这个公式就再也忘不掉了。2.2 为什么这道题非用二维前缀和不可激光炸弹这道题的数据范围通常是这样的目标点数量N最多到10000或者更多坐标范围在0到5000之间炸弹边长R也在0到5000之间。如果你用暴力枚举枚举炸弹的左上角位置然后遍历所有目标点看是否在炸弹范围内时间复杂度是O(N * 坐标范围^2)这个量级在竞赛中基本就是超时的命。而二维前缀和的优势在于它把“查询任意矩形区域和”这个操作的时间复杂度降到了O(1)。你只需要花O(坐标范围^2)的时间预处理出前缀和数组然后枚举所有可能的炸弹位置每个位置用O(1)时间查询总时间复杂度就是O(坐标范围^2 坐标范围^2)也就是O(坐标范围^2)。对于5000x5000的坐标范围这个量级是2500万次操作在C里跑起来毫无压力。这里有个关键点需要注意坐标范围是5000但目标点数量可能只有10000。这意味着整个平面上大部分位置是空的。有些同学会想那我能不能只对目标点做离散化把坐标压缩到10000以内理论上可以但离散化之后查询矩形和会变得非常麻烦因为你需要判断哪些目标点落在矩形内这又回到了暴力枚举的老路。所以对于这道题直接开一个5001x5001的二维数组做前缀和是最简单也最稳妥的做法。提示如果坐标范围再大一些比如到10^5那二维前缀和就开不下数组了这时候就需要考虑其他方法比如扫描线或者树状数组。但激光炸弹这道题的坐标范围设计就是专门为了让你用二维前缀和的。2.3 空间与时间的权衡取舍开一个5001x5001的int数组占用的内存大约是5001 * 5001 * 4字节也就是100MB左右。这个内存在大多数竞赛平台上都是可以接受的但如果你用的是Python那就要小心了。Python的列表嵌套列表存储int内存开销会大很多可能直接爆内存。所以如果你用Python写这道题我建议用numpy数组或者用array模块再或者用一维数组模拟二维数组把内存压缩到可接受的范围内。时间方面预处理前缀和需要遍历整个5001x5001的矩阵大概是2500万次加法操作。在C里这个操作大概需要0.1秒左右在Java里可能需要0.3秒在Python里如果用纯循环可能需要好几秒。所以如果你用Python一定要用numpy的cumsum函数来做前缀和速度会快几十倍。我个人的经验是这道题在C里写从读入数据到输出答案整个程序跑完不会超过0.5秒。但如果你在预处理阶段用了不必要的复杂操作比如每次都判断边界那时间就会成倍增加。所以写的时候要尽量简洁把边界判断放在循环外面或者用一些技巧来避免边界判断。3. 核心细节与实操要点3.1 坐标映射与数组下标处理激光炸弹这道题有一个非常容易踩的坑题目给出的坐标是从0开始的但我们在做前缀和的时候通常需要把下标整体加1这样才能方便地处理边界情况。比如题目说目标点在(0, 0)那我们在前缀和数组里应该把它存在(1, 1)的位置。这样做的原因是当我们需要查询以(0, 0)为左上角的矩形时公式里的x1-1和y1-1就会变成0而前缀和数组的第0行和第0列全是0正好可以参与运算不会出现下标越界的问题。具体操作是这样的读入一个目标点的坐标(x, y)和价值v然后执行pre[x1][y1] v。注意这里是而不是因为同一个位置可能有多个目标点。我见过有同学在这里用了结果同一个位置的目标点价值被覆盖了最后答案偏小还找不到原因。还有一个细节是炸弹的边长R可能大于坐标范围。比如坐标范围是5000但R是6000。这时候炸弹可以覆盖整个平面答案就是所有目标点的价值总和。如果你在枚举炸弹位置的时候循环的上界没有处理好可能会漏掉这种情况。我的处理方式是在枚举之前先判断一下如果R大于等于坐标范围的最大值就直接输出总和。或者更简单粗暴一点把坐标范围的上界设为max(5000, R)这样数组开大一点但逻辑上更统一。3.2 前缀和数组的构建技巧构建二维前缀和数组的标准做法是两层循环外层遍历行内层遍历列然后执行pre[i][j] pre[i-1][j] pre[i][j-1] - pre[i-1][j-1] a[i][j];这个公式的含义是当前位置的前缀和等于上方的前缀和加上左方的前缀和减去左上角重复计算的部分再加上当前位置的原始值。这个公式我建议你背下来因为它是二维前缀和的核心几乎所有二维前缀和的题都要用到它。但这里有一个优化技巧如果你不需要保留原始矩阵a可以直接在pre数组上做累加省掉一个数组的空间。具体做法是先把所有目标点的价值累加到pre数组的对应位置然后直接对pre数组做前缀和变换。这样你只需要一个二维数组内存占用减半。还有一个细节是循环的起始下标。因为我们在坐标映射的时候已经把下标整体加1了所以循环应该从1开始到坐标范围的上界结束。如果你从0开始循环那pre[i-1][j]就会访问到pre[-1][j]这是越界访问程序可能会崩溃或者得到错误结果。注意在C中全局数组会自动初始化为0所以不需要手动memset。但如果你用的是局部数组一定要记得初始化否则前缀和会出错。3.3 查询矩形和的边界处理查询矩形和的公式前面已经给过了但实际写的时候边界处理才是最容易出错的地方。假设我们要查询以(x1, y1)为左上角、(x2, y2)为右下角的矩形和其中x1和y1是原始坐标从0开始那在映射到前缀和数组之后查询的公式应该是sum pre[x21][y21] - pre[x1][y21] - pre[x21][y1] pre[x1][y1];注意这里的下标变化x21和y21对应的是右下角的映射后坐标而x1和y1对应的是左上角减1之后的映射后坐标。这个公式我建议你写个小函数封装起来这样主逻辑里调用的时候不容易写错。还有一个常见的错误是在枚举炸弹位置的时候循环的上界没有考虑炸弹的边长。假设炸弹的边长是R那炸弹的左上角坐标可以从0枚举到坐标范围-R。如果你枚举到了坐标范围那炸弹的右下角就会超出坐标范围查询的时候就会访问到数组之外的内存。所以循环的上界应该是max_coord - R 1其中max_coord是坐标范围的上界。我个人的习惯是在枚举之前先计算好有效的枚举范围然后用一个变量存起来这样循环条件写起来更清晰。比如int limit max_coord - R 1; for (int i 0; i limit; i) { for (int j 0; j limit; j) { // 查询以(i, j)为左上角、边长为R的矩形和 } }3.4 价值累加与重复点处理激光炸弹这道题有一个容易被忽略的细节同一个位置可能有多个目标点。如果你在读入数据的时候直接赋值而不是累加那后面的目标点就会覆盖前面的导致答案偏小。这个错误非常隐蔽因为样例数据通常不会在同一个位置放多个目标点所以你本地测试的时候可能发现不了但提交上去就会WA。正确的做法是在读入每个目标点的时候执行pre[x1][y1] v。这样即使同一个位置有多个目标点它们的价值也会被正确累加。还有一个相关的问题是如果炸弹的边长R是0那炸弹只能炸到一个点。这时候你需要特殊处理吗其实不需要因为R0的时候查询的矩形就是一个1x1的区域公式依然适用。但要注意循环的上界如果R0那limit max_coord 1循环会遍历所有位置这是正确的。我见过有同学在R0的时候把循环上界写成了max_coord - R结果漏掉了最后一个位置。所以写循环条件的时候一定要仔细最好用几个小例子验证一下。4. 完整实操流程与代码实现4.1 数据读入与坐标映射先来看数据读入部分。假设输入格式是第一行三个整数N、R、MAX_COORD分别表示目标点数量、炸弹边长、坐标范围的上界。接下来N行每行三个整数x、y、v表示一个目标点的坐标和价值。读入的时候我习惯用scanf而不是cin因为scanf在大量数据读入的时候速度更快。如果你用cin记得加上ios::sync_with_stdio(false)来加速。#include cstdio #include algorithm using namespace std; const int MAXN 5005; int pre[MAXN][MAXN]; int main() { int N, R; scanf(%d %d, N, R); int max_x 0, max_y 0; for (int i 0; i N; i) { int x, y, v; scanf(%d %d %d, x, y, v); pre[x1][y1] v; max_x max(max_x, x1); max_y max(max_y, y1); } // 后续处理 }这里我用max_x和max_y来记录实际用到的最大坐标而不是固定用5000。这样做的好处是如果坐标范围很小预处理的时间会大大减少。但要注意如果R很大max_x和max_y可能小于R这时候需要把上界扩展到R。4.2 前缀和数组的构建接下来构建前缀和数组。循环的范围应该是1到max_x和max_y而不是固定的5000。这样如果实际坐标范围很小预处理会快很多。for (int i 1; i max_x; i) { for (int j 1; j max_y; j) { pre[i][j] pre[i-1][j] pre[i][j-1] - pre[i-1][j-1] pre[i][j]; } }注意这里我直接在pre数组上做累加没有用额外的原始矩阵数组。这是因为我们在读入的时候已经把价值累加到了pre数组的对应位置所以pre数组的初始值就是原始矩阵的值。这样省掉了一个数组的空间。但这里有一个潜在的问题如果max_x和max_y小于R那炸弹可以覆盖整个平面答案就是pre[max_x][max_y]。但如果你在构建前缀和的时候只循环到max_x和max_y那pre数组在更大的范围内是没有值的。所以如果你要枚举炸弹位置需要把循环上界扩展到max(max_x, R)和max(max_y, R)。我的处理方式是在构建前缀和之前先把max_x和max_y扩展到至少为Rmax_x max(max_x, R); max_y max(max_y, R);然后再构建前缀和。这样pre数组在R的范围内都是有值的枚举的时候不会出问题。4.3 枚举炸弹位置与查询枚举炸弹位置的时候炸弹的左上角可以从0枚举到max_x - R从0枚举到max_y - R。对于每个位置查询以它为左上角、边长为R的矩形和。int ans 0; for (int i 0; i max_x - R; i) { for (int j 0; j max_y - R; j) { int x1 i, y1 j; int x2 i R - 1, y2 j R - 1; int sum pre[x21][y21] - pre[x1][y21] - pre[x21][y1] pre[x1][y1]; ans max(ans, sum); } } printf(%d\n, ans);这里要注意的是x2和y2的计算。因为炸弹的边长是R所以右下角的坐标是左上角坐标加上R-1。然后查询的时候右下角的映射后坐标是x21和y21左上角的映射后坐标是x1和y1因为x1和y1已经是原始坐标映射后坐标是x11和y11但查询公式里用的是x1和y1相当于减1之后的映射后坐标。这个下标关系我建议你在纸上画一遍确认无误之后再写代码。我当年就是在这里绕了好久最后画了个图才理清楚。4.4 完整代码与复杂度分析把上面的部分拼起来完整的代码如下#include cstdio #include algorithm using namespace std; const int MAXN 5005; int pre[MAXN][MAXN]; int main() { int N, R; scanf(%d %d, N, R); int max_x 0, max_y 0; for (int i 0; i N; i) { int x, y, v; scanf(%d %d %d, x, y, v); pre[x1][y1] v; max_x max(max_x, x1); max_y max(max_y, y1); } max_x max(max_x, R); max_y max(max_y, R); for (int i 1; i max_x; i) { for (int j 1; j max_y; j) { pre[i][j] pre[i-1][j] pre[i][j-1] - pre[i-1][j-1] pre[i][j]; } } int ans 0; for (int i 0; i max_x - R; i) { for (int j 0; j max_y - R; j) { int x1 i, y1 j; int x2 i R - 1, y2 j R - 1; int sum pre[x21][y21] - pre[x1][y21] - pre[x21][y1] pre[x1][y1]; ans max(ans, sum); } } printf(%d\n, ans); return 0; }时间复杂度方面预处理是O(max_x * max_y)枚举是O((max_x - R 1) * (max_y - R 1))两者都是O(坐标范围^2)的量级。对于5000的坐标范围总操作次数大约是2500万次在C里跑起来大概0.2到0.3秒。空间复杂度是O(max_x * max_y)也就是100MB左右。如果你用Python写我建议用numpy来做前缀和代码大概是这样import numpy as np N, R map(int, input().split()) MAX_COORD 5005 pre np.zeros((MAX_COORD, MAX_COORD), dtypenp.int32) max_x max_y 0 for _ in range(N): x, y, v map(int, input().split()) pre[x1][y1] v max_x max(max_x, x1) max_y max(max_y, y1) max_x max(max_x, R) max_y max(max_y, R) pre pre.cumsum(axis0).cumsum(axis1) ans 0 for i in range(max_x - R 1): for j in range(max_y - R 1): x1, y1 i, j x2, y2 i R - 1, j R - 1 s pre[x21][y21] - pre[x1][y21] - pre[x21][y1] pre[x1][y1] ans max(ans, s) print(ans)numpy的cumsum函数会直接在原数组上做累加速度非常快。但要注意numpy的int32可能会溢出如果价值总和很大建议用int64。5. 常见问题与排查技巧实录5.1 答案偏小或偏大的典型原因答案偏小是最常见的问题通常有以下几个原因。第一个是同一个位置的目标点价值被覆盖了没有用累加。这个前面已经强调过了读入的时候一定要用而不是。第二个是炸弹的边长R没有正确处理比如R大于坐标范围的时候循环上界没有扩展导致漏掉了覆盖整个平面的情况。第三个是查询矩形和的时候下标计算错误比如把x1和x2搞反了或者忘记加1减1。答案偏大则通常是重复计算了某些区域。比如查询公式里减去的部分没有正确减去或者加回了不该加的部分。我建议你在写查询公式的时候先在纸上画一个简单的例子手动算一遍然后再写代码。如果答案还是不对可以把中间结果打印出来和手动计算的结果对比。5.2 数组越界与内存超限数组越界是二维前缀和最容易出的问题。常见的情况包括循环从0开始导致访问pre[-1]查询的时候x21超出了数组范围或者max_x和max_y没有扩展到R导致枚举的时候越界。我的建议是在写代码之前先确定好数组的大小和循环的范围。数组大小至少要是坐标范围上界加2因为我们要把下标整体加1。循环的范围要仔细检查确保不会访问到数组之外的内存。内存超限通常发生在Python里因为Python的列表嵌套列表存储int的开销很大。如果你用Python写建议用numpy数组或者用一维数组模拟二维数组。一维数组模拟二维数组的做法是用pre[i * cols j]来代替pre[i][j]这样可以省掉嵌套列表的开销。5.3 时间超限的优化思路时间超限通常发生在预处理或枚举阶段。如果你用C写一般不会超时但如果你用了不必要的复杂操作比如在循环里做函数调用或者用了cin而没有加速那可能会超时。优化的思路有几个。第一用scanf代替cin或者给cin加上ios::sync_with_stdio(false)。第二把边界判断放在循环外面减少循环内的分支。第三如果坐标范围很大但目标点很少可以考虑离散化但离散化之后查询会变复杂需要权衡。第四用一维数组代替二维数组可以提高缓存命中率加快访问速度。我实测下来用C写这道题即使不做任何优化也能在0.5秒内跑完。但如果你用Java可能需要做一些优化比如用BufferedReader代替Scanner用StringBuilder代替字符串拼接。5.4 常见问题速查表问题现象可能原因排查方法解决方案答案偏小同一位置目标点价值被覆盖检查读入时是否用了改用累加价值答案偏小R大于坐标范围时漏算检查max_x和max_y是否扩展到R在构建前缀和前扩展上界答案偏大查询公式下标错误手动计算小例子对比重新推导查询公式数组越界循环从0开始或上界过大打印循环变量和数组下标调整循环起始和结束条件内存超限Python列表开销大查看内存占用改用numpy或一维数组时间超限预处理或枚举效率低计时各阶段耗时用scanf、减少分支、用一维数组提示如果你在本地测试的时候答案正确但提交上去WA那很可能是边界情况没有考虑到。建议自己构造几个边界测试用例比如N0、R0、R大于坐标范围、所有目标点在同一位置等逐一验证。5.5 独家避坑经验分享我在做这道题的时候踩过最大的坑是坐标映射。一开始我没有把坐标加1直接用了原始坐标结果查询的时候x1-1变成了-1数组越界。后来我把坐标加1之后又忘了在查询公式里对应调整导致答案偏大。这个坑我花了大概一个小时才爬出来所以后来我养成了一个习惯只要涉及二维前缀和先在纸上画一个3x3的格子标上坐标然后手动走一遍读入、构建、查询的流程确认无误之后再写代码。另一个坑是R的处理。有一次我写的代码在R0的时候答案正确但R大于坐标范围的时候就错了。后来发现是因为我在构建前缀和的时候只循环到了max_x和max_y没有扩展到R导致枚举的时候访问到了未初始化的内存。这个问题的隐蔽性在于未初始化的内存通常是0所以答案不会崩溃但会偏小。解决方法是在构建前缀和之前先把max_x和max_y扩展到至少为R。还有一个经验是如果你用C写全局数组会自动初始化为0但如果你在函数里开了大数组一定要记得初始化。我见过有同学在main函数里开了5000x5000的数组没有初始化结果前缀和全是随机值答案自然也是错的。所以要么用全局数组要么用memset手动初始化。最后分享一个小技巧如果你不确定自己的查询公式是否正确可以写一个暴力版本的程序随机生成小规模数据然后和你的前缀和版本对比。如果两个版本的结果一致那你的公式大概率是对的。这个方法我用了很多次非常有效。6. 从这道题延伸出去的知识点激光炸弹虽然是一道基础题但它涉及的知识点可以延伸到很多方向。比如如果你把炸弹的边长R改成不固定而是可以任意选择那问题就变成了求最大子矩阵和这时候就需要用到动态规划或者单调栈。如果你把二维平面改成三维空间那前缀和就变成了三维前缀和公式会更复杂但思路是一样的。还有一个延伸方向是如果目标点的数量非常大但坐标范围很小那你可以用二维前缀和直接做。但如果坐标范围非常大目标点数量也很大那你就需要考虑离散化或者扫描线。扫描线的思路是把炸弹的左右边界看作事件用线段树维护当前覆盖的目标点价值总和然后滑动窗口求最大值。这个思路在计算几何和数据结构里都很常见。我个人的建议是先把二维前缀和练熟然后再去学扫描线和线段树。因为二维前缀和是基础基础不牢后面学更复杂的东西会很吃力。而且二维前缀和的思路在很多实际问题里都有应用比如图像处理里的积分图就是二维前缀和的直接应用。如果你做图像处理需要快速计算任意矩形区域的像素和那二维前缀和就是你的不二之选。我在实际工作中就遇到过这样的场景需要从一个大的遥感图像里快速计算任意区域的植被指数平均值。如果每次都用暴力遍历那速度慢得没法用。后来我用了二维前缀和把预处理时间控制在几秒内之后每次查询都是毫秒级效率提升了几百倍。所以别看这道题简单它的实用价值一点都不低。