刷题刷到前缀和这一章的时候几乎每本算法竞赛进阶教材都会把激光炸弹放在第一个例题。这道题没有复杂的算法也没有恶心的数据结构但它的信息量很大二维前缀和公式、坐标平移、覆盖边长、枚举边界每个环节都藏着出题人的小心思。我当年第一次交这道题连续WA了四发最后发现不是公式背错了而是“坐标从0开始”和“炸弹到底炸几个点”这两个细节没理清楚。这篇博客就把这道题从头到尾拆开题目在考什么、二维前缀和为什么能解决、边界条件怎么理解、完整代码怎么写以及我实测踩过的一些坑。适合刚学完基础语法、开始接触区间问题的竞赛新人也适合想快速复习前缀和套路的老人。1. 先看清题目激光炸弹到底在考什么1.1 题目在讲什么、数据范围暗示了什么先看题目在说什么。地上有一张可以认为是无限大的地图上面有N个目标每个目标在整数坐标(x, y)处价值为w。现在有一颗边长为R的炸弹炸到的是一个正方形区域并且包含边界。你可以把炸弹放在任意位置要使得被炸毁的目标总价值最大。听起来像是一个“放位置、算覆盖”的几何题但实际上所有坐标都是整数、所有目标都是点所以它本质上是一个二维区间统计问题。数据范围是决定一切的地方。坐标范围0到5000N不超过10000R可以大到离谱。我为什么先强调这个因为竞赛题里数据范围就是算法的路标。如果坐标只有几百暴力枚举也能过当坐标到5000你还能勉强用O(5000²)级别的算法当坐标到1e5二维的O(n²)就凉了得换离散化或者扫描线。而激光炸弹故意把坐标限制在5000就是在告诉你用二维数组用O(5000²)的预处理这就是正确的方向。另外一个容易被忽略的点是目标之间可能重叠。题目并没有保证每个坐标上只有一个目标所以读入的时候同一个格子可能有多个目标价值需要累加。这一点看起来不痛不痒但在代码里如果写成赋值而不是累加就会在隐藏数据上翻车。后面我会专门再讲。1.2 朴素做法为什么走不通暴力做法为什么不行最直白的思路是枚举炸弹位置。炸弹能放在哪因为所有目标都是整数点炸弹的边只要对齐到整数坐标附近就能覆盖到目标所以需要考虑的位置大约是5001×5001种。如果你每一个位置都去遍历一遍N个目标复杂度就是5001² × 10000粗略算一下超过2.5×10¹¹次运算这在任何OJ上都是不可能通过的。就算你换一种思路枚举每一对目标判断它们能不能被同一个炸弹覆盖然后统计覆盖范围内的价值最坏情况下也要处理N²对目标10000²等于1e8这已经勉强了但还要处理坐标范围带来的额外复杂度整体还是不可控。更关键的是这种思路写起来非常别扭边界情况一多代码很快就变成一团乱麻。所以核心矛盾很清楚目标数量不算多但地图范围很大。我们需要一个数据结构能快速回答“任意矩形区域内目标价值之和”预处理一次之后每次查询都是O(1)。这就是二维前缀和。这道题之所以经典就是因为它把“用空间换时间”这个思想表现得非常直白先花O(MAX²)构建前缀和矩阵再用O(1)回答每个窗口的查询最终枚举所有窗口也只需要O(MAX²)的代价。2. 二维前缀和这道题的加速核心2.1 一维前缀和快速热身前缀和这个概念大家从一维数组就接触过。设原数组a[1…n]前缀和数组S[i] S[i-1] a[i]要查区间[l, r]的和答案就是S[r] - S[l-1]。这里有个常用技巧让S[0] 0这样l1的时候S[0]参与运算不会出问题。生活化的理解就是记账本你记下每个月末的累计消费想知道某几个月一共花了多少用两个月末的累计值相减就行了。一维前缀和把“区间求和”的复杂度从O(n)降到了O(1)代价是O(n)的预处理。激光炸弹这道题要处理的是二维平面上的矩形区域所以需要把一维思路推广到二维。2.2 二维前缀和公式与容斥原理二维前缀和是一维的自然推广。定义一个二维数组SS[i][j]表示从(1,1)到(i,j)这个矩形区域里所有目标价值之和。那怎么高效地计算S有公式S[i][j] S[i-1][j] S[i][j-1] - S[i-1][j-1] a[i][j]这个公式用容斥的角度看特别清楚S[i-1][j]是“上面一整块”的和S[i][j-1]是“左面一整块”的和把这两块并在一起时左上角那个S[i-1][j-1]被重复计算了一次所以要减掉最后再加上当前格子的值a[i][j]。查询任意子矩阵时假设左上角是(x1, y1)右下角是(x2, y2)则sum S[x2][y2] - S[x1-1][y2] - S[x2][y1-1] S[x1-1][y1-1]道理和构建时一样用大矩形减去上边条、左边条但左上角那一块被减了两次需要加回来一次。我第一次学的时候觉得这个公式很绕后来想通一个点就不怕了你永远只需要记住“被重叠计算的部分要扣掉被重复扣除的部分要加回”。前缀和的所有公式本质上都是这个原则在二维平面上的投影。2.3 原地构建前缀和的实用技巧构建二维前缀和时有个实现上的优化可以不用额外开一个S数组直接在原数组上原地做。读入阶段先用a[i][j]存每个格子的价值构建阶段再让a[i][j] a[i-1][j] a[i][j-1] - a[i-1][j-1]。因为遍历顺序是从左到右、从上到下等你处理到a[i][j]时a[i-1][j]和a[i][j-1]都已经变成前缀和形式了不会冲突。这样空间减半代码也省事。顺序为什么必须是i从小到大、j从小到大因为更新s[i][j]用到的s[i-1][j]在上一行s[i][j-1]在左边一列只有按这个顺序遍历才能保证它们已经被更新过了。如果你把j循环放外层变成按列遍历那s[i-1][j]还没有被算出来结果就会全错。这个细节很隐蔽我见过好几个同学在多重循环调换顺序之后debug很久才发现问题。3. 激光炸弹的边界处理最容易翻车的地方3.1 坐标从0开始统一平移是标准操作第一个坑坐标从0开始。题目给的是0 ≤ x, y ≤ 5000但二维前缀和的公式天然要求下标至少从1开始因为要访问i-1和j-1。如果你硬要处理0下标就得单独初始化第0行和第0列很容易乱。标准做法是把所有点坐标整体加1让它们落到1..5001区间。这样第0行、第0列天然是0当作哨兵所有公式照常使用。具体来说读入(x, y)时实际存到s[x1][y1]里。不要小看这一步很多新手在这里踩坑之后才意识到前缀和的下标习惯不是随便定的。为什么非要留一组0哨兵因为查询公式里有x1-1、y1-1这样的下标如果x1最小是1那下标0就必须存在且为0否则就会越界或者读到垃圾值。3.2 R×R还是(R-1)×(R-1)窗口定义决定代码第二个坑也是最核心的坑炸弹覆盖的到底是几个点。题目说炸弹能摧毁边长为R的正方形包含边界。很多人第一反应是那覆盖的整数点个数应该是(R-1)×(R-1)不对。你可以想一个最简单的例子R1。如果边长是1炸弹覆盖的是一个点还是一个零面积区域显然是一个点因为题目说“包含边界”边长为1的正方形正好包含一个整数格点。再看R2如果炸弹覆盖范围在x方向横跨两个整数坐标、y方向也横跨两个整数坐标那覆盖到的整数点是2×24个。所以边长R的正方形覆盖的整数点数是R×R个不是(R-1)×(R-1)个。对应到矩形求和公式里窗口的右下角是(i,j)左上角是(i-R1, j-R1)下标差是R。子矩阵和的写法就是s[i][j] - s[i-R][j] - s[i][j-R] s[i-R][j-R]。我在这个细节上WA过不止一次写代码前先把这个理清能省好几发提交。很多人把“边长”和“格子数量”混在一起以为边长R对应R-1个间隔这个误区一定要掰过来。3.3 R比地图还大时怎么办第三个坑R可能比地图还大。题目里R的取值范围可以非常大如果R已经大于整个地图的尺寸那么一颗炸弹就能覆盖所有目标答案就是所有目标的价值总和。如果不做特判枚举窗口的循环可能根本不会执行答案就会变成0。我见过的最稳写法是读入时顺便累加total预处理完最大坐标maxCoord之后如果R maxCoord直接输出total。另一种写法是把R取min(R, maxCoord)把它压到地图大小这样窗口正好能框住全图。两种都行第一种更好理解第二种写起来更短。我个人习惯用第一种因为在推导边界条件时思路更直白不容易把自己绕晕。还有一个隐藏细节如果R非常大大到ull都存不下那肯定远大于5001此时特判分支一定会命中所以根本不会用R去做数组下标。这也是为什么必须把特判放在前缀和构建和窗口枚举之前。4. 完整代码实现与关键细节解读4.1 参考代码下面给一版可以直接过的参考代码。我用的是C风格但核心思想不依赖语言。先说设计读入时把坐标加1存到全局数组s里同时记录所有点中最大的横坐标和纵坐标记为maxX和maxY这样数组实际需要计算的范围就是max(maxX, maxY)如果坐标集中在小区域能省不少常数。关于R大于地图范围的情况用提前输出total来处理。#include bits/stdc.h using namespace std; const int MAXN 5005; int s[MAXN][MAXN]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, r; cin n r; int maxX 0, maxY 0; long long total 0; for (int i 0; i n; i) { int x, y, v; cin x y v; // 坐标整体1留出0行0列作为哨兵 int nx x 1; int ny y 1; s[nx][ny] v; // 同一个坐标可能有多个目标必须累加 maxX max(maxX, nx); maxY max(maxY, ny); total v; } int m max(maxX, maxY); // 实际需要计算的矩阵范围 // 如果R已经能覆盖整个地图答案就是所有目标价值之和 if (r m) { cout total \n; return 0; } // 原地构建二维前缀和 for (int i 1; i m; i) { for (int j 1; j m; j) { s[i][j] s[i - 1][j] s[i][j - 1] - s[i - 1][j - 1]; } } long long ans 0; // 枚举所有可能的R*R窗口注意右下角至少是R for (int i r; i m; i) { for (int j r; j m; j) { long long cur s[i][j] - s[i - r][j] - s[i][j - r] s[i - r][j - r]; ans max(ans, cur); } } cout ans \n; return 0; }4.2 逐段解读代码中的关键选择有几个地方值得细说。第一s数组是全局量默认全0所以第0行、第0列天然是0哨兵不需要初始化。这比在函数内部开局部数组要安全得多局部大数组容易爆栈全局数组则放在静态区不用担心这个问题。第二s[nx][ny] v不能用等号。题目没说每个坐标只出现一次所以同一点上可能有多个目标。我一开始用等号样例都能过但交上去全WA后来加了组数据把两个目标放在同一坐标就暴露了。这是个非常经典的测试点写题解的人通常都会提到但自己踩一遍印象才最深。第三构建前缀和的循环顺序不能换。i从小到大、j从小到大保证在处理s[i][j]时s[i-1][j]和s[i][j-1]已经是更新过的前缀和。如果你把j循环放在外层等于按列处理结果就全错了。第四枚举窗口时循环从r开始。为什么不是从1开始因为窗口右下角至少要到达R才能构成一个完整的R×R窗口。如果从1开始一方面会访问到s[i-r]这种负下标造成数组越界另一方面算出来的矩形不满一个R×R不是合法答案。4.3 复杂度分析与适用前提时间的复杂度是O(n m²)其中m是实际计算范围最大不超过5001。读入N个目标需要O(n)构建前缀和需要O(m²)枚举窗口需要O((m-r1)²)最坏也是O(m²)。m5001时5001²约2500万对C来说就是几十毫秒级别的运算完全在时限内。这也是激光炸弹能成为入门板题的底气二维数组开满5005×5005内存大概100MB大多数OJ都能接受。如果哪天你把坐标上限换成1e5这种算法就彻底失效了。所以每次遇到二维区间题先看坐标范围再决定要不要用二维前缀和。5. 常见问题与避坑实录5.1 WA原因速查表整理一下我见过、踩过的报错场景做成一张速查表方便你提交前对照检查。现象可能原因处理方式样例能过交上去WA同一坐标多个目标用了而非读入时用s[x][y] v输出总是偏大前缀和公式里的容斥项S[i-1][j-1]没减检查构建公式是否完整结果偏小甚至为0R大于地图范围未处理提前输出total或把R压到m数组越界/段错误窗口循环从1开始导致下标i-r为负循环从r开始边界数据R1出错把覆盖点数写成(R-1)×(R-1)明确是R×R下标差为R结果不稳定随机错局部数组过大导致栈溢出把数组声明为全局5.2 实测过的边界测试数据实践出真知。我在学习这道题的时候反复用几组极端数据来检查代码的健壮性一组是两个目标叠在同一个坐标比如(1,1)价值5和(1,1)价值10R1正确答案应该是15。这个测试的价值在于强制你确认自己的读入逻辑用的是累加。如果我用等号这组数据会输出10当场暴露问题。一组是R等于1只炸一个格子。这个测试的价值在于验证你对窗口定义的理解R×R在下标差上体现为R窗口左上角和右下角差R-1个下标但下标差是R。如果这组数据输出正确说明公式基本没问题。一组是R非常大远大于地图范围比如R100000000地图上只有(0,0)一个点价值7。正确答案是7。这组数据验证特判分支是否正确触达。还有一组是所有目标分布在对角线上横纵坐标都很大用来验证动态计算m的逻辑是否能把整个地图框住。5.3 性能与读入优化的小经验性能方面实测下来5000²的前缀和构建在普通机器上也就几十毫秒整个程序不会成为瓶颈。但如果题目加大到1e4×1e4O(n²)就hold不住了那时候才需要考虑其他方案。读入方面的一个小习惯N只有1e4我一般直接cin配ios::sync_with_stdio(false)没必要上快读。如果哪天你在别的题里看到有人用快读先别急着模仿要看数据量到底值不值。同步关闭后的cin在1e4量级和scanf几乎没有区别代码更简短。数组开多大也是一个有讲究的问题。我开5005不是随手写的坐标最大值5000平移后是5001你要访问s[5001][5001]所以数组长度至少是5002留到5005只是凑个整。如果你在别处看到有人开5001×5001访问下标5001时会越界这种代码能不能过纯看运气。6. 从激光炸弹延伸到更多场景6.1 差分是前缀和的镜像操作激光炸弹除了让你背会二维前缀和公式更大的价值是让你建立起一种思维模型二维区间问题可以通过预处理变成O(1)查询。顺着这个思路往后走你会发现差分其实是前缀和的逆运算。一维差分提供这样一个技巧对数组的区间[l,r]加一个值v只需要在d[l] vd[r1] - v最后做一次前缀和就能还原出真实数组。二维差分也类似对矩形区域加值时在四个角上做标记最后做二维前缀和得到每个位置的真实值。激光炸弹如果反过来问给定很多个矩形区域每个区域有个价值问所有区域叠加后某个点的最大值是多少这就是二维差分的典型场景。很多竞赛题就是前缀和与差分配套出现的一正一反覆盖了竞赛里一大类区间修改与区间查询问题。学完前缀和之后花半小时把差分也过一遍性价比极高。6.2 坐标范围变大时的思路切换另外激光炸弹的坐标范围小可以用二维数组硬顶如果哪天遇到坐标范围上亿的区间统计题二维数组就开不下了。这时候要么离散化把出现过的坐标压缩成小下标要么换扫描线思路把二维区间统计拆成一维事件排序。前者是前缀和的延伸后者已经是另一个领域了。我建议先把激光炸弹这类板题做扎实碰到坐标范围大的题你才有底气去判断该走哪条路。竞赛里很多题目不是考你某个单一算法而是考你在多个可行方案之间做取舍的能力。前缀和、差分、离散化、扫描线这些工具放在工具箱里用的时候才知道哪个顺手。6.3 我个人的练习建议最后分享一个我个人的练习习惯。学完这道题后我不会急着刷下一题而是先自己默写一遍代码确保在没有任何提示的情况下能写出前缀和的构建和查询公式。然后我会造几组极限测试数据R1、R超过地图、所有目标集中在同一个点、目标沿斜对角线分布。这些极限数据能帮你把边界条件彻底吃透。竞赛考场上最大的敌人不是算法难而是你没见过自己代码的崩溃方式。激光炸弹这道题你越早把边界坑踩明白后面的二维区间DP、矩阵求和类问题就越轻松。我自己的体会是一道好的板题值得反复写三遍第一遍照着写第二遍关着书默写第三遍试着改造它去解决别的问题。等你做到第三遍的时候二维前缀和就不再是公式而是你手里的一块积木了。