企业官网建设流程全解析

先说说结论：想刷明白GESP五级，二维前缀和这道坎绕不过去；想学会二维前缀和，洛谷P2004《领地选择》是我见过最合适的入门题。题目不长，逻辑直白，但把二维前缀和的核心思想、边界处理、坐标映射全考了一遍，做透这一道，等于把这一整类题的路子都摸清了。

如果你正在备考GESP五级认证，或者刚开始接触C++竞赛算法，想找一个能完整理解“二维前缀和”这个知识点的标准模板题，这篇内容应该能帮到你。我会从题目本身的设定讲起，先拆一维前缀和，再推到二维，给出一份能直接过评测机的完整C++代码，最后把我在洛谷评论区和自己身上踩过的那些坑列成一张排查清单。整篇文章不需要你有多深的算法基础，只要会C++基本语法、知道二维数组怎么读怎么写，就能跟上节奏。

1. 认识题目：领地选择到底在让你做什么

1.1 还原P2004的原始需求

先从题面说起。P2004的设定非常直白：你有一块n行m列的矩形土地，每个格子里有一个数值，代表这个地块的“产出”或者“价值”。现在你要在这块土地上选一个正好c行c列的正方形区域作为领地，目标是让这块领地的产出总和最大。输入第一行是n、m、c，接下来n行每行有m个数，最后输出你选中的那块领地左上角的坐标，格式是x y。

这道题最容易被忽略的是输出条件：如果有多个正方形区域都取得了最大值，题目要求输出x最小的那个，也就是行号最小、越靠上越好；如果行号也并列，再输出y最小的，也就是列号最小、越靠左越好。

这里还有一个非常具体的细节陷阱：输出的坐标是左上角的坐标，不是右下角，更不是中心点。我在第一次做这道题的时候，公式推得毫无问题，前缀和数组也建对了，最后却把右下角的坐标当成了答案交上去，白白WA了一次。这种细节在竞赛题里非常常见，读题阶段就得拿笔画下来，否则调试半天都找不到问题所在。

1.2 为什么这道题适合当二维前缀和入门题

选P2004练二维前缀和，是因为它把“前缀和”这种抽象概念变成了一个特别具体的决策问题：你要在所有可能的c×c窗口里找一个总和最大的。而“求任意一个子矩形的数字总和”正是二维前缀和最擅长的操作。这道题没有引入贪心、二分、状态压缩等其他算法，就是单纯考察你能不能把区间求和从O(c²)优化成O(1)，非常纯粹。

而且它的数据规模决定了你必须用前缀和。假设n、m分别到1000，c也有几百，如果暴力枚举每个左上角再一层层数格子，计算量至少达到十亿级别，评测机能给你的结果只有TLE。反过来用二维前缀和，整个算法只需要遍历两遍矩阵，时间复杂度O(nm)，空间复杂度O(nm)，在竞赛环境下是一个极其标准的解法。

适合人群也很明确：备考GESP五级的学生、刚接触竞赛算法想打基础的选手，或者单纯想把二维前缀和从“背公式”变成“真会用”的C++学习者。这道题做完，你收获的不止是一份AC代码，而是一整套处理二维区间求和的思维方法。

2. 从暴力到前缀和：一步步找到最优解

2.1 先暖身：一维前缀和的思路

二维前缀和不是凭空出现的，它是一维前缀和的自然扩展。我们先把问题降维：假设只有一行格子，长度是M，每个位置v[j]有一个数，你想快速知道区间[l, r]这一段的和，怎么做？

最容易想到的办法是预处理一个前缀数组S，S[j]表示前j个数的总和，递推公式是：

S[j] = S[j - 1] + v[j]

那么区间[l, r]的和就等于：

S[r] - S[l - 1]

这里的核心思想是“用减法代替多步加法”。原来要一个一个累加r-l+1个数字，现在只需要查两次前缀表，再做一次减法。代价是第一次遍历时要多存一个累加数组，本质上就是空间换时间。

我经常用一个生活化的类比来理解它：你记了一个“本月累计支出账本”，想知道3月到7月一共花了多少，只用拿“到7月为止的累计支出”减去“到2月为止的累计支出”就行了，不用把3月、4月、5月、6月、7月的账单一张张翻出来加一遍。

2.2 暴力枚举为什么不可行

回到二维领地问题。在没接触前缀和之前，正常人第一反应是三重甚至四重循环：

• 枚举每一个左上角(x, y)；
• 枚举这个c×c正方形里的每个格子，把值累加；
• 和当前最优值比较，更新答案。

用复杂度说话：可能的左上角一共有(n - c + 1) × (m - c + 1)个，接近n×m量级；每个窗口里又有c×c个格子要做加法。所以总复杂度是O(n×m×c²)。

这个数字有多恐怖？取n=m=500、c=250来算一下：

500 × 500 × 250 × 250 = 1.56 × 10¹⁰

也就是说，大约156亿次加法。即使评测机一秒能执行一亿次左右的基础操作，也至少要跑一百多秒，远远超过普通题目的时限。GESP真题和洛谷题目的数据规模往往会给到1000甚至更大，暴力解法根本没有生存空间。

不过暴力解法在竞赛中也不是完全没用。它的正确性一目了然，非常适合用来写一个“对拍程序”：先跑暴力拿到小数据的正确答案，再跑前缀和版本，对比两者的输出。这是我刷题时最常用的验证手段，后面会详细展开。

2.3 二维前缀和公式是怎么来的

现在把一维的思想扩展到二维。定义一个二维前缀和数组P[i][j]，它表示以(1, 1)为左上角、以(i, j)为右下角的这个大矩形的所有格子总和。注意，坐标从1开始，这样在处理边界时不需要额外判断空值，这是写这类代码最重要的一个小技巧。

那P[i][j]怎么递推？可以把它拆成三块来看：

• 上面那一大块是P[i-1][j]，也就是以(1,1)为左上角、(i-1,j)为右下角的矩形；
• 左边那一大块是P[i][j-1]，也就是以(1,1)为左上角、(i,j-1)为右下角的矩形；
• 再加上当前格子的值v[i][j]。

如果把P[i-1][j]和P[i][j-1]直接相加，左上角那块P[i-1][j-1]会被加两次，等于多算了一遍。所以再减掉一个P[i-1][j-1]。于是得到递推式：

P[i][j] = P[i-1][j] + P[i][j-1] - P[i-1][j-1] + v[i][j]

这个式子本质上是容斥原理：加上下边这块，加上右边这块，多减掉重叠的那块。很多同学会死记这个公式，但一旦题目稍微变个条件，比如从(0,0)开始存数组，公式的角标全变了，立刻就懵。我建议第一次学的同学拿出一张格子纸，在3×3的小方格上把P[2][3]拆成P[1][3]、P[2][2]、P[2][2]重叠的样子画出来，亲手推一遍，比背十遍公式都管用。

求任意子矩形和时也一样。假设要求左上角为(a, b)、右下角为(c, d)的矩形总和，仍然用容斥：

ans = P[c][d] - P[a-1][d] - P[c][b-1] + P[a-1][b-1]

大矩形P[c][d]先减去上方多出来的P[a-1][d]这块，再减去左方多出来的P[c][b-1]这块，此时左上角P[a-1][b-1]被减了两次，所以要加回来一次。

2.4 用一个小例子手算一遍

光说公式有点干，我来带一个具体数据。假设n=3、m=3、c=2，矩阵长这样：

1 2 3 4 5 6 7 8 9

第一步，建前缀和数组P。我直接给出填充好的结果：

P[1][1] = 1 P[1][2] = 1 + 2 = 3 P[1][3] = 3 + 3 = 6 P[2][1] = 1 + 4 = 5 P[2][2] = 5 + 3 - 1 + 5 = 12，也就是左上角2×2的和1+2+4+5=12 P[2][3] = P[1][3] + P[2][2] - P[1][2] + 6 = 6 + 12 - 3 + 6 = 21，对应1+2+3+4+5+6=21 P[3][1] = 12 P[3][2] = P[2][2] + P[3][1] - P[2][1] + 8 = 12 + 12 - 5 + 8 = 27，对应第1列到第2列全部行的和 P[3][3] = P[2][3] + P[3][2] - P[2][2] + 9 = 21 + 27 - 12 + 9 = 45，也就是全部9个格子加起来正好等于45

现在枚举右下角。c=2，所以右下角从(2,2)开始。先看以(2,2)为右下角的2×2窗口，左上角是(1,1)：

cur = P[2][2] - P[0][2] - P[2][0] + P[0][0] = 12 - 0 - 0 + 0 = 12

再看以(2,3)为右下角、左上角为(1,2)的窗口：

cur = P[2][3] - P[0][3] - P[2][1] + P[0][1] = 21 - 0 - 5 + 0 = 16

对应格子2+3+5+6=16，完全正确。如果你能跟着手算到这里，说明二维前缀和的核心逻辑你已经掌握了。

2.5 结合P2004的求值方式

在这道题里，我们枚举的是正方形的右下角(i, j)，那么左上角就是(i-c+1, j-c+1)。套用子矩形求和公式，得到：

sum = P[i][j] - P[i-c][j] - P[i][j-c] + P[i-c][j-c]

注意这里为什么减的是P[i-c][j]而不是P[i-c+1][j]？因为左上角是第i-c+1行，那么它上面那一行的下标是i-c，也就是矩形之外紧挨着的上一行。列方向同理。这个边界极容易出错，我每次写代码的时候都习惯先写出左上角坐标，再反推出要减的下标，而不是硬记公式。硬记的话，变量一多，很容易把减号的下标写混。

3. C++完整代码与逐行解析

3.1 一份能直接AC的代码

下面给出我平时用的写法，这份代码在洛谷P2004上可以直接通过：

#include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m, c; cin >> n >> m >> c; vector<vector<ll>> pref(n + 1, vector<ll>(m + 1, 0)); for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { ll val; cin >> val; pref[i][j] = pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1] + val; } } ll best = LLONG_MIN; int ansX = 1, ansY = 1; for (int i = c; i <= n; i++) { for (int j = c; j <= m; j++) { ll cur = pref[i][j] - pref[i - c][j] - pref[i][j - c] + pref[i - c][j - c]; if (cur > best) { best = cur; ansX = i - c + 1; ansY = j - c + 1; } } } cout << ansX << " " << ansY << "\n"; return 0; }

3.2 读入与前缀数组的类型选择

第一个值得注意的点是数据类型。题目矩阵里的每个值不一定都是小整数，当n和m都到1000时，一个c×c区域的和可能轻松超过int能表示的范围，尤其GESP这种练习里评测数据往往喜欢压极端值。一旦溢出，结果可能变成负数，你的答案更新逻辑就全部乱套。所以前缀和数组务必使用long long，这是血泪教训。我见过不少人在评论区贴出WA代码，原因就是int溢出。

读入优化那句ios::sync_with_stdio(false)和cin.tie(nullptr)也非常关键。cin读入1000×1000个数字，如果不关同步，在数据量大时性能差异很明显。虽然这道题数据规模下不关多半也能过，但养成习惯总是好的。如果你更习惯scanf和printf，也完全可以，两者的性能峰值差不了太多，选自己顺手的就好。

3.3 坐标是怎么映射的

遍历部分我枚举的是右下角，从(c, c)一直枚举到(n, m)。为什么从c开始？因为如果i小于c，那左上角i-c+1就会小于等于0，超出了土地范围。同理列方向从c到m。

算出当前窗口和cur后，和best做比较。关键点来了：我用的是严格大于号cur > best，而不是大于等于。配合遍历顺序从上到下、从左到右，这个写法天然满足了题目“输出x最小、若并列再输出y最小”的要求。

原因是：假设某个坐标是先遇到的解，后面又遇到了一个值相同的解，由于cur > best是false，后者不会覆盖前者，所以最后保存的永远是“第一个”达到最大值的解。如果你写成cur >= best，那新解会不断覆盖旧解，最终输出的反而是靠下靠右的坐标，直接WA。这个隐藏考点，题解区很少有人说明白，但恰恰是最容易踩的。

更新坐标时，左上角等于右下角减边长再加1：

ansX = i - c + 1 ansY = j - c + 1

输出顺序是先x后y，也就是先行后列，不要搞反。P2004要求输出x y，新手非常容易按y x输出，白白错一次。

3.4 如果不用vector，直接用传统二维数组

上面用了vector<vector >，好处是灵活、不必手动管理内存。如果你更习惯传统数组，可以写成：

const int MAXN = 1005; ll pref[MAXN][MAXN];

有一点要特别提醒：MAXN要根据题目规模适当放宽。比如n最大是1000，至少开1005，因为我们的代码会访问到pref[i-c][j]这类下标，当i等于c时访问的是pref[0][j]，这个0行0列正好是外围的一圈0，必须保留。使用vector后所有值初始化为0，使用全局数组时也是自动初始化为0，这些边界情况就被统一处理了。

3.5 空间与常数的进一步优化

如果你对空间敏感，可以只开一个数组，把原始矩阵直接读进pref的同一个数组里，边读边构建前缀和，不需要额外存一份原始矩阵。上面的代码就是这么干的：读入val后直接累加进pref[i][j]，省掉了一个存储原始矩阵的数组，空间占用直接减半。

再进一步，如果你追求极致的缓存友好，可以把vector<vector >换成一维数组模拟二维：

vector<ll> pref((n + 1) * (m + 1), 0); auto get = [&](int x, int y) -> ll { return pref[x * (m + 1) + y]; };

不过在P2004这道题上，vector<vector >的性能已经完全够用，没必要为了常数优化把代码写得难读。竞赛里有一个朴素的原则：先保证正确，再优化性能；先写能AC的代码，再谈常数。过度优化的代码逻辑复杂，反而不利于考试时快速排查bug。

4. 评测路上的常见坑与排错方法

4.1 我踩过的几个典型错误

我在刷P2004和同类题目时，反反复复遇到过下面几种错误，整理成一张速查表：

其中一个特别隐蔽的坑是初始化best。如果字段里有负数，而且负得很多，你把best初始化为0，那么答案区间可能根本无法更新，最后输出一个错误坐标。所以稳妥做法是初始化为LLONG_MIN，也就是long long能表示的最小值，保证第一个窗口必然能更新答案。不要觉得全负数据离你很远，评测数据就是为了专门卡这种细节而存在的。

4.2 自己造小数据验证，永远是对的

在交评测之前，我强烈建议先自己造几个边界数据跑一遍。尤其是这三种：

• n=1, m=1, c=1：只有一个格子，输出(1,1)；
• n=3, m=3, c=2：手算一遍所有2×2窗口的和，看看坐标映射对不对；
• 矩阵里全填同一个负数，比如全部-5：观察best初始化和严格大于是否还能正常工作。

造数据时可以写一个测试代码，把暴力结果和前缀和版本的结果并列打印对比。这个方法在碰到任何二维前缀和题目时都适用，等于多了一道保险。可以说，我在竞赛练习中最重要的习惯就是“写一个显然正确但更慢的解法对拍”，这个习惯帮我省了无数Debug时间。

4.3 调试时的printf大法

如果WA了，别急着改代码，先在关键位置加输出。比如在更新答案的循环里临时打印每个窗口的左上角、右下角和当前值：

cerr << "check (" << i - c + 1 << "," << j - c + 1 << ") -> (" << i << "," << j << ") sum=" << cur << "\n";

这个输出能让你一眼看出是否有窗口被漏算，或者是否坐标映射出错。在GESP或洛谷环境中，调试输出建议用cerr，因为它和正常输出cout分开，不会影响最终的评测结果打印。本地调试完记得把调试输出删干净，不然多打印一串东西照样WA。

4.4 GESP五级上机考试时的注意点

如果是在GESP认证或类似上机环境中做这道题，我额外提醒三点。

第一，环境里可能没有自动补全和语法高亮，平时就要习惯完整手写代码。不要把vector<vector >这种长类型写错，一旦编译报错，在考试中会浪费宝贵时间。

第二，尽量保持代码可读性。GESP认证一般运行通过即得分，但万一你的代码有隐藏bug，清晰简洁的代码能让你在最后几分钟快速定位。命名就用pref、cur、best这类语义明确的词，不要搞一堆a、b、c1、c2之类的变量名。

第三，时间充裕时，务必用暴力代码对拍。特别是当你对题目的输出规则不确定时，对拍能立刻验证你的理解是否正确。比如P2004“输出x最小再y最小”这个规则，很多人一开始会忽略，对拍数据一旦构造出并列情况，马上就能发现问题。

5. 从P2004延伸：二维前缀和的进阶用法

5.1 可变形题盘点

把P2004吃透之后，你能做的题目一下就拓宽了。二维前缀和最常见的延展有这么几种。

第一种是窗口大小不固定。比如求整个矩阵中和最大的子矩形，但没有指定边长。这时单靠一个前缀和做所有窗口枚举就不合理了，因为窗口数量会变成O(n²m²)级别，通常要借助其他技巧，例如把行压缩成一维前缀和，再对列方向做一维最大子段和。

第二种是带查询的题目。给你很多组查询，每次问某个子矩形的和。前缀和方案的优势在这种场景下体现得淋漓尽致：预处理一次O(nm)，之后每次查询O(1)，完全不用重复遍历矩阵。这是二维前缀和最直接的应用场景，也是GESP和各类竞赛爱出的形式。

第三种是三维前缀和。原理还是容斥，只是变成了在三个维度上做加加减减，公式比二维多几项，但思路完全一致。有兴趣的同学可以自己研究一下怎么计算一个三维长方体块内的总和，这对理解容斥思想非常有帮助。

5.2 配合差分一起理解

前缀和有一个“好兄弟”叫差分。简单说，差分是前缀和的逆运算：如果给你一个矩阵和一堆“矩形区域加上某个数”的修改，可以用二维差分在O(1)时间内完成每次修改，最后做一遍前缀和还原出真实数值。P2004练的是查询，差分练的是修改。把两者结合起来，你能解决一大类区间操作问题，这也是很多进阶教程把“二维前缀和与差分”放在一起讲的原因。

我建议学完P2004之后，去找几道二维差分的题做一做。你会发现，前缀和构建时那个递推式，和差分的更新式在形式上几乎是对称的，理解了其中一个，另一个就是镜像问题。

5.3 给备考GESP五级的同学的一点学习顺序建议

如果你正在备考GESP五级，二维前缀和通常和矩阵、坐标、枚举这类题放在一起考。我的建议是把学习拆成三步：

• 第一步，把一维前缀和的原理彻底想清楚，最好能自己推导区间和公式；
• 第二步，用P2004把二维前缀和的公式和边界处理彻底搞懂；
• 第三步，找两三道带矩形查询的题目练手，熟悉不同输入格式下的写法。

每个阶段写代码时都坚持“先想复杂度，再写循环”的习惯。遇到TLE，先别急着优化常数，而是回头想想算法复杂度是不是选高了。前缀和这类题的魅力就在于，它用很小的空间开销换来了巨大的时间收益，这种思维本身就是竞赛算法训练中最值得培养的东西。

最后再分享一个小技巧：如果你在考场上一时忘了二维前缀和的公式，别慌，在草稿纸上画一个3×3或4×4的小矩阵，把P[i-1][j]、P[i][j-1]、P[i-1][j-1]分别标注出来，推一遍式子只需要一分钟。这比硬背公式可靠得多，也更能避免因为角标混乱导致的边界错误。我在实际做题中用过很多次这个方法，每次都有效。