企业官网建设流程全解析

1. 题目到底在说什么：拆解题意与考点定位

1.1 题意逐句拆解

先说说洛谷P2280 [HNOI2003] 激光炸弹这道题。凡是刷到二维前缀和这个标签的人，十有八九会被各路题解推荐先做这道题，它确实当得起"二维前缀和入门教科书"这个称号。

题目背景很简单：有一种激光炸弹，能炸掉边长为R的正方形范围内的所有目标，现在地图上有N个目标点，每个点有一个价值，问一次轰炸最多能拿到多少总价值。

拆开看有三个关键信息：

• 目标点是离散的，坐标范围是0到5000的整数，可能有多个目标落在同一个坐标点上
• 炸弹的杀伤范围是"边长为R的正方形"，这里的R是一个整数
• 目标是求最大值，不是求方案数，也不是求有多少个点被覆盖

很多新手第一眼看到这道题会往扫描线、线段树那个方向想，因为"求固定边长矩形内权值和最大值"这个表述确实也有数据结构的解法。但请注意题目给出的约束条件：坐标范围固定为5000，N最大是10^4，R不超过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-R+1, j-R+1)。那为什么公式里是s[i-R][j]而不是s[i-R+1][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够吗？如果偏移后最大下标是5001，5005就已经留了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]，前者一定爆，后者勉强但卡边。
• 第二步，检查是否做了坐标偏移。如果没偏移，枚举时的下标会出现-1，C++运行时不会立刻崩溃，但前缀和递推时的非法访问会读入不可预期的垃圾值，后续计算全部出错，运气差的时候表现为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个整数刻度的。比如R=1时，炸弹能摧毁的就是一个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_x，y坐标同样处理成1..cnt_y，然后在压缩后的网格上做二维前缀和。

但这里有个非常重要的问题：离散化压缩的是坐标点，正方形覆盖关系在压缩之后会失真。因为原本两个坐标之间的距离可能很大，压缩后变成了相邻整数，导致一个R×R的方块覆盖的坐标点集合和压缩前不一致。

针对"固定边长矩形覆盖最大权值"这个具体问题，离散化之后通常配合扫描线加线段树来解决，而不是压缩坐标后继续用二维前缀和。方向是对的，但工具要升级。如果只是去洛谷刷模板题，不需要掌握这么多，但如果你想把这类题目做深，这个点值得研究。

6.2 相关经典题目推荐

二维前缀和不是孤立的知识点，它和很多经典问题串在一起。刷完这道题之后，我建议按这个顺序继续深入：

• 一维前缀和的变体题，巩固对"区间和查询"的理解
• 二维前缀和的矩阵区域查询题，熟悉离线静态查询的各种写法
• 前缀和配合二分答案的题目，体会"用前缀和快速check一个答案是否可行"的思路
• 如果对差分感兴趣，还可以看二维差分的题目，差分和前缀和是一对互逆操作，理解了差分能反过来加深你对前缀和的理解

我实际带刷题的经验是：一个人如果能把激光炸弹这道题的代码完全不用看题解默写出来，并能在五分钟内讲清楚为什么查询公式是"二加一减"，那他对二维前缀和就真正入门了。

7. 最后分享几点实际刷题经验

这道题我前前后后刷过不止一遍，每次带新人重新讲一遍都有新体会，说几个实用经验。

第一个经验：不要小看坐标偏移。很多人觉得这题难在算法，其实难在下标映射。说到底，这道题对算法思维的要求并不高，真正考的是你能不能把数学上的矩形区域和计算机里的二维数组下标严格对应起来。做题时先画坐标纸，把偏移前后的对应关系写在草稿上，再动手写代码，效率会高很多。

第二个经验：一定要自己手推一遍前缀和表格。我建议你拿一个3×3的小矩阵，用笔算出s数组的每一个值，再手算一次查询区域的和，对比代码输出的结果。这个动作只需要五分钟，但比看十篇题解都管用。我真见过不少人公式背得滚瓜烂熟，结果把递推里的加号写成减号的低级错误。

第三个经验：提交之前要重点检查三条边界。一是R等于1的极端情况，此时程序应退化成单点查询；二是R大于坐标范围的情况，此时答案应为全图总价值；三是多个目标落在同一点的情况，此时输入是重复坐标，程序必须输出累加后的结果。把这三条边界测完，你基本可以放心提交。

第四个经验：洛谷的讨论区是很好的学习资源。如果你WA了又实在找不到原因，去讨论区翻一翻别人踩过的坑，往往一两分钟就能定位问题。但要注意，讨论区看思路可以，看代码要谨慎筛选，别直接复制，因为很多人写的代码风格并不规范，带着坏习惯的代码反而会误导你。

把二维前缀和这个工具彻底吃透之后，再回头看激光炸弹这道题，你会发现它其实非常温柔：数据结构简单、思维量适中、坑点集中，是一个完美的入门题。后续遇到更复杂的前缀和变形题，比如带修改的二维前缀和、三维前缀和、前缀和与离线查询结合，整个思路都是从这里生长出去的。基础打得牢，后面才走得远——这句话在算法训练里是百试百灵的真理。