1. 题目到底在说什么拆解题意与考点定位1.1 题意逐句拆解先说说洛谷P2280 [HNOI2003] 激光炸弹这道题。凡是刷到二维前缀和这个标签的人十有八九会被各路题解推荐先做这道题它确实当得起二维前缀和入门教科书这个称号。题目背景很简单有一种激光炸弹能炸掉边长为R的正方形范围内的所有目标现在地图上有N个目标点每个点有一个价值问一次轰炸最多能拿到多少总价值。拆开看有三个关键信息目标点是离散的坐标范围是0到5000的整数可能有多个目标落在同一个坐标点上炸弹的杀伤范围是边长为R的正方形这里的R是一个整数目标是求最大值不是求方案数也不是求有多少个点被覆盖很多新手第一眼看到这道题会往扫描线、线段树那个方向想因为求固定边长矩形内权值和最大值这个表述确实也有数据结构的解法。但请注意题目给出的约束条件坐标范围固定为5000N最大是10^4R不超过5000。这个数据范围本身就是最强提示——二维数组能开下暴力枚举每个R*R方块在时间上也完全承受得起。1.2 考点分析为什么二维前缀和是正解先做个复杂度推导。如果直接暴力对每一个可能放置炸弹的位置去统计范围内所有目标的价值复杂度大约是坐标范围的两个维度乘以单次查询的开销。坐标范围是5000×5000光是枚举所有可能位置就是约2.5×10^7个候选点如果每个点再去遍历范围内的目标最坏情况会炸穿时间限制。二维前缀和的做法把问题分成了两步预处理阶段用O(X×Y)的代价也就是5000×5000规模的循环算出一张二维前缀和表查询阶段对任意一个R×R正方形用O(1)的时间取出区间和这样总复杂度从暴力的O(X×Y×N级别)降到了O(X×Y)对这道题的数据范围来说就是在几百毫秒以内出结果。更进一步这题的坐标范围和R都是固定的不需要离散化、不需要动态维护二维前缀和就是最匹配的工具。2. 从一维到二维前缀和思想是怎么一步步演化来的2.1 一维前缀和的回顾在理解二维前缀和之前先把一维的原理复习一遍。给定一个数组a[1..n]要反复询问区间[l,r]的和如果每次临时累加单次查询是O(n)的。前缀和的做法是预处理出一个新数组pre其中pre[i]表示a[1]a[2]...a[i]那么区间和sum(l,r) pre[r] - pre[l-1]。这里有个细节值得强调pre[i]表达的是从开头加到i的历史总和它天然包含了重复计算的中间部分。所以区间查询要做减法把前缀中不属于[l,r]的那一段减掉。这个思想推广到二维是完全一样的逻辑——只不过减的东西从一个数变成了两个方向的重叠区域。2.2 二维前缀和的递推公式二维前缀和定义成s[i][j]表示所有横坐标不超过i、纵坐标不超过j的目标价值累加和。可以理解成从左上角(0,0)到右下角(i,j)这个矩形内所有数的总和。计算s[i][j]的递推公式是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]就得到了完整的矩形和。这个容斥的思想是整个二维前缀和的灵魂。很多人背公式的时候不理解为什么要减左上角那一块结果一到变形题目就懵。只要你画一个3×3的格子手动推一遍把每个格子的值代入递推式走两轮就永远不会忘。2.3 正方形区域查询公式有了s数组之后想查询从(x1,y1)到(x2,y2)这个矩形区域内目标价值的和公式是ans s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] s[x1-1][y1-1]这和递推式是对称的容斥关系大的整体减去左边部分减去上边部分左上角被减掉了两次所以要加回来一次。放到激光炸弹这道题里正方形的两个顶点就是(i-R, j-R)和(i, j)也就是以(i,j)为右下角、边长为R的方块。实际枚举时我习惯用这样的写法value s[i][j] - s[i-R][j] - s[i][j-R] s[i-R][j-R]注意这里下标都是从0开始而且R×R的范围意味着如果右下角是(i,j)左上角就是(i-R1, j-R1)。那为什么公式里是s[i-R][j]而不是s[i-R1][j]因为前缀和数组本身存的是到某个坐标为止的所有点之和我们想排除的是左上角那个点之前的区域。画一条坐标轴坐标真正意义上的点是整数但当我们用s数组来表达区间时(i-R, j)恰好就是(0,0)到(i-R,j)这个子矩形的右下角。这里的处理方式取决于你如何映射坐标也正是后面要说的坑点之一。3. 核心代码实现预处理与枚举的全过程3.1 数据读入与累加第一步是把目标点的价值写进二维数组。这里直接建一个全局数组s既用来存原始值又用来滚动变成前缀和可以省掉一个a数组。洛谷上的常见写法是给坐标做偏移也就是把坐标整体加1再存入这样后续枚举从1开始避免处理边界时下标变成负数。坐标范围是0到5000加1偏移之后最大到5001数组至少要开5005×5005。我习惯多留一点余量开成5005或者5010省得边界问题导致RE。多个目标落在同一个点上的情况直接累加即可int n, r; cin n r; for (int i 0; i n; i) { int x, y, v; cin x y v; s[x 1][y 1] v; }这里用plus one偏移还有一个附带好处因为下标从1开始枚举过程中的s[x][0]和s[0][y]天然是0省去了对边界位置的特殊判断。很多人的代码喜欢在全局变量里开数组因为全局数组默认清零省掉一层memset。3.2 前缀和预处理接下来用两层循环把s数组原地改造成前缀和for (int i 1; i 5001; i) { for (int j 1; j 5001; j) { s[i][j] s[i - 1][j] s[i][j - 1] - s[i - 1][j - 1]; } }注意这里使用的是复合赋值写法因为s[i][j]原本存的是该点的原始价值。如果使用原始坐标不偏移那么i从0开始循环时会出现s[-1]访问C数组负下标不会直接报错但读的是垃圾数据这是新手最容易踩的坑。为什么预处理循环上界是5001而不是5000因为坐标偏移之后最大坐标变成了5001而坐标为5001这一行其实对应原始坐标5000。如果循环只跑到5000偏移后的最后一行一列永远没有参与累加查询结果会整体偏小。3.3 枚举R×R正方形预处理完成后枚举所有可能放置炸弹的右下角位置计算每个正方形区域的价值和更新答案int ans 0; for (int i r; i 5001; i) { for (int j r; j 5001; j) { int val s[i][j] - s[i - r][j] - s[i][j - r] s[i - r][j - r]; if (val ans) ans val; } } cout ans endl;这里又有一个细节为什么i从r而不是从1开始因为枚举的是以(i,j)为右下角的r×r方块如果i小于r正方形就会超出地图上边界这种位置不合法。实际上超出边界的方块也不是不能计算只是它包含的区域不足r×r我们要的是完整正方形所以直接跳过。这部分的时间复杂度是两层循环约2500万次C跑下来不到0.1秒完全在合理范围内。整个算法的核心逻辑到这里就结束了大约三十行代码。3.4 完整参考代码把上面的片段拼起来一份可以直接提交的代码长这样#include bits/stdc.h using namespace std; const int MAX 5005; int s[MAX][MAX]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, r; cin n r; for (int i 0; i n; i) { int x, y, v; cin x y v; s[x 1][y 1] v; } for (int i 1; i 5001; i) { for (int j 1; j 5001; 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 5001; i) { for (int j r; j 5001; j) { int val s[i][j] - s[i - r][j] - s[i][j - r] s[i - r][j - r]; ans max(ans, val); } } cout ans endl; return 0; }提示如果你提交后出现RE优先检查数组是否开小如果出现WA优先检查坐标偏移和枚举边界。4. 这道题的隐藏坑点新手最容易挂的地方4.1 边界坐标与数组大小的坑原题给出的坐标范围是0 ≤ x, y ≤ 5000这意味着坐标0是合法位置。如果直接拿原始坐标建前缀和查询s[i-r]在i-r等于-1时就越界了。我见过不少人在这个地方反复改代码一开始用原始坐标写完发现边界处理特别绕改成if判断又觉得代码难看。最简洁的方案就是整体偏移把0映射到1。这样s数组的1..5001行都对应原始坐标0..5000查询公式里的下标永远保持非负不需要任何特判。数组大小方面开5005是最低要求。有人会问5005够吗如果偏移后最大下标是50015005就已经留了4个余量。但如果你在枚举时将上界写成了5005而不是5001这时访问到的行是垃圾区域里面的值基本是0对答案影响不大只是白跑了一些循环。真正致命的是数组开成505或者5001这种刚好卡边的尺寸一旦循环边界有偏差就RE。4.2 R超出地图范围的坑原题的R没有任何保证说一定小于等于5000如果R比坐标范围还大那情况就变了。比如地图最大坐标只有100但R给成了1000此时任何位置的r×r正方形都会超出地图范围。这个问题的标准处理方式有两种第一种是限制枚举上界把循环里的5001改成min(5001, r其实不行)——不对实际上更标准的做法是在读入R之后做一个钳制如果R大于5001就把R设成5001。因为地图本身的有效范围只有5000×5000炸弹范围再大能覆盖到的也就是整个地图。第二种是在枚举时用max(1, 5001-r)之类的方式限制起点但这样代码变得啰嗦。我推荐第一种。具体写法就是在读入R之后加一行if (r 5001) r 5001;这样后面的逻辑完全不用改直接跑就能过。这道题的数据里R会不会超过5000我不确定但作为一个严谨的解法这个边界条件应当处理。4.3 重复目标点累加的坑题目里没有明确说每个坐标最多只有一个目标。实际上多个目标可能出现在同一个坐标点上这时候如果直接赋值而不是累加会丢掉之前的目标价值。我见过的最隐蔽的一个错误是有人用s[x 1][y 1] v而不是 v导致同一个点上的多个目标只算了最后一个。由于测试数据里确实存在重复点这种做法会输出偏小的答案。判断一个坐标是否存在多个目标可以想象成仓库里同一货架上堆了好几箱货盘点时要把每个箱子都算进去不能只记录最上面那一箱。这就是为什么必须是而不是。5. 常见报错与排查实录5.1 运行错误RE排查RE大概率出在数组越界上。拿到RE之后先做三件事第一步检查数组声明大小。s[5005][5005]是最低配置如果你写的s[500][500]或者s[5050][5050]前者一定爆后者勉强但卡边。第二步检查是否做了坐标偏移。如果没偏移枚举时的下标会出现-1C运行时不会立刻崩溃但前缀和递推时的非法访问会读入不可预期的垃圾值后续计算全部出错运气差的时候表现为RE。第三步检查R是否过大。如果R是5000枚举循环是i从5000到5001没问题。但如果R在极端数据下超过5001而且你没有做钳制那么i-r可能出现负数。这里唯一安全的方法是前面说的对R做min处理。5.2 答案错误WA排查WA比RE更折磨人因为程序能跑但答案不对。遇到WA按以下顺序排查第一确认坐标偏移是否到位。比如原始输入是(5000, 5000)在数组里存放的位置是(5001, 5001)如果你在枚举时遍历到5000就停止这个点就永远不会被纳入计算。第二确认前缀和递推的写法是累加不是覆盖。很多人把递推写成s[i][j] s[i-1][j] s[i][j-1] - s[i-1][j-1]这会把当前点的原始值直接覆盖掉相当于丢掉了一个点的价值。必须用或者在右侧加上s[i][j]本身。第三确认正方形区域查询是否多算了边界。这里要特别留意激光炸弹的R×R范围在坐标上是包含R个整数刻度的。比如R1时炸弹能摧毁的就是一个1×1的点也就是一个坐标。如果使用偏移坐标枚举到(i,j)时查询s[i][j] - s[i-1][j] - s[i][j-1] s[i-1][j-1]正好取到单个点的值这才对。很多题解把这种处理叫虚拟网格或点阵坐标其实不需要记这些名词你只要清楚s[i][j]表达的是坐标轴上某个矩形区域的和查询公式里的每一项对应哪一块区域就不会错。5.3 一个让我印象深刻的调试经历以前我给学弟调这题代码的时候发现他的程序在本地跑样例全对交到洛谷上就WA一片。我一看他的代码枚举时循环上界写的是MAXH 5000但他做坐标偏移时把输入坐标都加了1所以最大有效坐标变成了5001。等于说整个最后一行永远是0只要答案涉及纵坐标或横坐标为5000的目标点就一定会漏。这个例子说明一个道理坐标系偏移不是一个可以随便加的选择它必须贯穿整个程序。读入时偏移了预处理和枚举的边界就要跟着偏移后坐标的最大值走。最简单的方法是在读入过程中维护最大坐标值然后所有循环边界都用这个最大值而不是写死。实际改良版int maxCoord 0; for (int i 0; i n; i) { int x, y, v; cin x y v; s[x 1][y 1] v; maxCoord max(maxCoord, max(x 1, y 1)); } // 但要注意maxCoord至少要和r相等否则枚举范围不足 maxCoord max(maxCoord, r);有了maxCoord之后预处理和枚举循环都跑到maxCoord就行这样代码容错性更高也方便以后迁移到其他坐标范围不固定的类似题目中。比写死5001要灵活。6. 进阶思考如果题目不那么模板怎么办6.1 坐标稀疏时的离散化思路激光炸弹这题之所以能用二维前缀和直接莽根本原因是坐标范围只有5000×5000二维数组能完整装下。但如果把坐标范围放大到10^9级别还是同样的题意二维前缀和就没法直接用了——你会因为没有那么大的连续数组空间而卡住。这时候就需要离散化。离散化听上去高级本质就是把稀疏的坐标压缩成连续的稠密坐标。具体做法是把所有出现过的x坐标去重排序映射成1..cnt_xy坐标同样处理成1..cnt_y然后在压缩后的网格上做二维前缀和。但这里有个非常重要的问题离散化压缩的是坐标点正方形覆盖关系在压缩之后会失真。因为原本两个坐标之间的距离可能很大压缩后变成了相邻整数导致一个R×R的方块覆盖的坐标点集合和压缩前不一致。针对固定边长矩形覆盖最大权值这个具体问题离散化之后通常配合扫描线加线段树来解决而不是压缩坐标后继续用二维前缀和。方向是对的但工具要升级。如果只是去洛谷刷模板题不需要掌握这么多但如果你想把这类题目做深这个点值得研究。6.2 相关经典题目推荐二维前缀和不是孤立的知识点它和很多经典问题串在一起。刷完这道题之后我建议按这个顺序继续深入一维前缀和的变体题巩固对区间和查询的理解二维前缀和的矩阵区域查询题熟悉离线静态查询的各种写法前缀和配合二分答案的题目体会用前缀和快速check一个答案是否可行的思路如果对差分感兴趣还可以看二维差分的题目差分和前缀和是一对互逆操作理解了差分能反过来加深你对前缀和的理解我实际带刷题的经验是一个人如果能把激光炸弹这道题的代码完全不用看题解默写出来并能在五分钟内讲清楚为什么查询公式是二加一减那他对二维前缀和就真正入门了。7. 最后分享几点实际刷题经验这道题我前前后后刷过不止一遍每次带新人重新讲一遍都有新体会说几个实用经验。第一个经验不要小看坐标偏移。很多人觉得这题难在算法其实难在下标映射。说到底这道题对算法思维的要求并不高真正考的是你能不能把数学上的矩形区域和计算机里的二维数组下标严格对应起来。做题时先画坐标纸把偏移前后的对应关系写在草稿上再动手写代码效率会高很多。第二个经验一定要自己手推一遍前缀和表格。我建议你拿一个3×3的小矩阵用笔算出s数组的每一个值再手算一次查询区域的和对比代码输出的结果。这个动作只需要五分钟但比看十篇题解都管用。我真见过不少人公式背得滚瓜烂熟结果把递推里的加号写成减号的低级错误。第三个经验提交之前要重点检查三条边界。一是R等于1的极端情况此时程序应退化成单点查询二是R大于坐标范围的情况此时答案应为全图总价值三是多个目标落在同一点的情况此时输入是重复坐标程序必须输出累加后的结果。把这三条边界测完你基本可以放心提交。第四个经验洛谷的讨论区是很好的学习资源。如果你WA了又实在找不到原因去讨论区翻一翻别人踩过的坑往往一两分钟就能定位问题。但要注意讨论区看思路可以看代码要谨慎筛选别直接复制因为很多人写的代码风格并不规范带着坏习惯的代码反而会误导你。把二维前缀和这个工具彻底吃透之后再回头看激光炸弹这道题你会发现它其实非常温柔数据结构简单、思维量适中、坑点集中是一个完美的入门题。后续遇到更复杂的前缀和变形题比如带修改的二维前缀和、三维前缀和、前缀和与离线查询结合整个思路都是从这里生长出去的。基础打得牢后面才走得远——这句话在算法训练里是百试百灵的真理。