如果你正在备考GESP五级或者刚好卡在洛谷P2004领地选择这道题上那这篇文章就是写给你看的。作为一个带着学生反复刷过这道题的C竞赛教练我可以直接告诉你结论这题表面是“选一块正方形领地”本质考的只有一件事——二维前缀和。而且它还是五级考纲里矩阵类问题的基础模板搞懂了它后面一连串题目都会轻松不少。文章里我会把从读题、公式推导、完整代码到各种隐蔽的坑全部过一遍保证你看完能直接照着敲而不是看完还只会背公式。1. 先读懂题面它到底在问什么1.1 题目描述与考点洛谷P2004领地说到底就是一个矩阵求区域和的问题。给你一个 n×m 的方格地图每个格子里有一个数值这个数值可以理解为这块地的收益可能为正也可能为负。题目给了一个固定边长 c让你选一块边长为 c 的正方形领地要求这块领地内所有格子数值加起来最大最后输出这块正方形左上角的坐标。如果有多个区域的和相同就输出行号、列号都更靠左上角的那个。坐标从 1 开始计数。这题在GESP五级里的定位非常典型。五级考纲已经不像四级那样只考一维数组、简单模拟而是要开始接触矩阵、递推、基础算法优化这些内容。二维前缀和就是最好的过渡题目它不涉及高深的算法思想却极其考验你对二维下标的控制力和对递推关系的理解。你会在读题过程中发现题目本身没有复杂的数学包装就是把“求若干次子矩阵和”这个需求赤裸裸地摆在你面前你能想到用多快的办法去求就决定了你是AC还是TLE。很多同学第一次做这题会犯一个方向性错误想当然地以为这就是要枚举所有正方形然后把里面的每个格子的值加一遍。确实在没有任何前置知识的情况下这种暴力思路最符合直觉。但题目给的 n、m 通常能到 1000 这个级别靠两三层循环硬算时间复杂度会高到无法接受。所以做题的第一步不是急着写代码而是先判断数据规模思考有没有能让“求一个子矩形和”变成 O(1) 操作的办法。1.2 暴力思路为什么会超时我们来算一笔账。假设 nm1000c500你要枚举所有可能的边长 c 的正方形左上角。横向可选的左边界有 n-c1 个也就是 501 个纵向同样是 501 个所以正方形个数约 25 万个。每个正方形内部有 c×c250000 个格子加起来就是 250000×250000大约 625 亿次加法运算。这还是在没有任何多余判断的乐观情况下实际跑起来必然是超时的。就算你把 c 缩小到 100计算量也有约 81 亿次对于普通评测环境来说依旧是天文数字。这里我常跟学生打一个比方一维前缀和就像你记流水账先算出从月初到当前日的累计花费之后想知道某几天的花费用累计数相减就行。二维前缀和就是把这个思想扩展到平面上提前把每个“从左上角到当前格子的矩形总和”算好存起来。后面随便问你哪个子矩阵的和你都可以通过几次简单的加减法直接得到结果不用再回矩阵里一格一格累加。P2004这道题的核心价值就在这里它逼你建立“预处理换查询速度”的意识这种意识在后面的动态规划、线段树等高级算法里还会反复出现。2. 二维前缀和核心原理与公式推导2.1 从一维前缀和说起要理解二维前缀和先得把一维版本刻在脑子里。假设有一个数组 a[1]、a[2]……a[n]定义 pre[i]pre[i-1]a[i]那么 pre[i] 就表示 a[1] 到 a[i] 的和。想知道 a[l] 到 a[r] 的和不需要循环累加直接算 pre[r]-pre[l-1] 就行。减掉 pre[l-1] 的本质是把前 l-1 个数字的影响从总和中扣除。二维情况完全同理只是从“一条线”变成了“一个面”。我们用一个二维数组 pre[i][j] 来表示从坐标 (1,1) 到坐标 (i,j) 这个矩形范围内所有格子的数值总和。只要你把这张“累计表”完整地建出来之后任何一个子矩形都能用这张表上四个角的值通过加减组合得到结果。这里要提醒一下为了让边界处理简单代码里最好让矩阵下标从 1 开始而不是从 0 开始。很多从基础C语法转过来的同学习惯了数组从 0 开始但在这个问题上从 0 开始意味着 pre[-1] 这种不存在的下标会频繁出现最后被迫写一堆 if 特判。我推荐的通用写法是先开 n1 行、m1 列的数组让第 0 行第 0 列全部保持 0这样公式可以无脑套用不需要额外判断。2.2 预处理表的含义与递推公式二维前缀和的核心递推公式是pre[i][j] a[i][j] pre[i-1][j] pre[i][j-1] - pre[i-1][j-1]很多初学者第一次看到这个公式会懵为什么加了两块大的又要减回去一块我们画个示意图来看。pre[i-1][j] 是第 1 行到第 i-1 行、第 1 列到第 j 列这个矩形的总和pre[i][j-1] 是第 1 行到第 i 行、第 1 列到第 j-1 列这个矩形的总和。把这两块加起来你会发现从 (1,1) 到 (i-1,j-1) 的那块矩形被算了两次。而我们想要的是 (1,1) 到 (i,j) 的完整矩形这个完整矩形其实等于上方的大矩形加上左侧的大矩形再加上当前格子 a[i][j]但重叠的左上角被重复加了所以要减掉一次 pre[i-1][j-1]。这个推导过程我强烈建议你自己在草稿纸上画一个 4×4 的方格图把每个区域用不同颜色标出来。我带的不少学生反映这个公式如果只看不画三天后必忘但凡自己推过一次之后就像骑自行车一样不会忘。本质上它就是一个二维的容斥原理和多米诺骨牌覆盖、集合交并计算面积这些场景是一模一样的思路。2.3 正方形和查询公式建好 pre 表之后题目要求的“以 (x,y) 为左上角、边长为 c 的正方形区域和”就可以这样算。这个正方形的右下角坐标是 (x2,y2)其中 x2xc-1y2yc-1。整块区域的和等于sum pre[x2][y2] - pre[x-1][y2] - pre[x2][y-1] pre[x-1][y-1]理解和刚才的递推公式是镜像的pre[x2][y2] 是从左上角到右下角的大矩形的总和但我们只想要其中一小块。先减掉这个大方块上方的部分 pre[x-1][y2]再减掉左边的部分 pre[x2][y-1]这时候左上角那一小块被减了两次所以要加回来 pre[x-1][y-1]。四个值三次减法一次加法查询复杂度 O(1)。注意这里的坐标 x、y 是正方形的左上角而正方形也可能贴着地图右边界和下边界。所以枚举 x 的范围是 1 到 n-c1y 的范围是 1 到 m-c1。这是很多人在循环边界上出错的地方少了这个“1”你最后一行或者最后一列的正方形就永远扫不到。3. P2004 完整落地读入、建表、查询、输出3.1 代码选型与数据范围判断写这个题之前先确认两件事数组开多大用什么类型存。洛谷P2004的数据范围里n、m 最高能到 1000那么一种稳妥的开法就是long long pre[1005][1005]多开几个单位防止边界擦碰。为什么不建议开动态二维 vector不是不行而是比赛场景下静态数组更省心不会因为 vector 的初始化方式不对导致下标访问出问题。静态数组开在全局区也能自动清零正好满足 pre[0][] 和 pre[][0] 为 0 的需求。类型选择上我建议直接无脑用 long long。虽然单个格子的数值可能不会大到溢出 int但子矩阵里有一千乘一千个格子累加之后完全可能超过 21 亿。一旦你用 int 存前缀和轻则答案错误重则溢出成负数。这个坑我在带学生做题时见过不下十次明明算法完全正确就因为类型开小了挂得莫名其妙。用 long long 最多就是多占一倍内存1005×1005 的 long long 数组才 8MB 左右完全不是负担。3.2 完整 C 代码下面这份代码严格按照“读入即建表、查询即比较、严格大于才更新”的流程写是我给学生使用的标准模板。#include bits/stdc.h using namespace std; long long pre[1005][1005]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m, c; cin n m c; for (int i 1; i n; i) { for (int j 1; j m; j) { cin pre[i][j]; pre[i][j] pre[i - 1][j] pre[i][j - 1] - pre[i - 1][j - 1]; } } long long best LLONG_MIN; int ansX 1, ansY 1; for (int x 1; x c - 1 n; x) { for (int y 1; y c - 1 m; y) { int x2 x c - 1; int y2 y c - 1; long long sum pre[x2][y2] - pre[x - 1][y2] - pre[x2][y - 1] pre[x - 1][y - 1]; if (sum best) { best sum; ansX x; ansY y; } } } cout ansX ansY \n; return 0; }这段代码的流程非常直接读入每个格子的值顺手就把它所在的二维前缀和算出来然后两层循环枚举所有可能的左上角坐标每个坐标用 O(1) 公式算出正方形区域和最后和当前最大比较记录更优的坐标。如果你之前在别的地方见过类似代码大概率也是这个结构但结构相似不代表细节都对下面我把每个关键点单独拿出来说。3.3 逐段拆解关键代码第一件事读入优化。ios::sync_with_stdio(false); cin.tie(nullptr);这两行很多人知道要写但不理解为什么要写。cin 默认要和 C 语言的 scanf 保持同步这个同步过程会让每次读入都变慢。在 10^6 级别的数据量下不关同步的 cin 很可能直接让你 TLE。关掉之后 cin 的速度基本能接近 scanf刷题足够用了。当然你用 scanf 也不是不行但既然用了 C 的流就把优化开到位。第二件事读入即建表。循环里先cin pre[i][j]接着pre[i][j] pre[i-1][j] pre[i][j-1] - pre[i-1][j-1]。为什么不单独开一个 a 数组存原始矩阵因为没必要。你读完一个格子的值以后原始值除了用来算前缀和之外再也没有其他用途完全可以在原地累加。这种写法省内存也减少一层循环理解负担。但要注意读入顺序必须是逐行、逐列从左到右这样当处理到 (i,j) 时(i-1,j) 和 (i,j-1) 这两个位置的前缀和一定已经算好了。第三件事枚举右边界。循环条件写成x c - 1 n千万不要写x n - c。如果你用“起点从 0 开始数”的习惯很容易把边界搞错一位。因为坐标从 1 开始最后一个合法左上角的行号是 n-c1。为了让自己不犯错我建议直接在循环头里写x n - c 1语义一目了然。y 同理。第四件事更新答案时用严格大于sum best。这一点极其重要稍后我会专门讲为什么。3.4 手动推演一个小样例纸上谈兵再多不如一个小样例来得直观。假设 n3m3c2矩阵如下1 2 3 4 5 6 7 8 9先算前缀和表。pre[1][1]1。pre[1][2]213。pre[1][3]336。pre[2][1]415。pre[2][2]553-112。pre[2][3]6126-321。pre[3][1]7512。pre[3][2]8125-124。pre[3][3]92421-1242。然后枚举所有边长为 2 的正方形。左上角 (1,1)右下角 (2,2)区域和是 pre[2][2]-pre[0][2]-pre[2][0]pre[0][0]12。左上角 (1,2)右下角 (2,3)区域和是 21-pre[0][3]? 不对按公式是 pre[2][3]-pre[0][3]-pre[2][1]pre[0][1]21-0-5016。左上角 (2,1)右下角 (3,2)区域和是 pre[3][2]-pre[1][2]-pre[3][0]pre[1][0]24-3-0021? 等一下这里我口算可能不准不过没关系你可以自己拿草稿纸核对。肉眼直接相加左上角 (2,1) 的 2×2 是 457824。啊对pre[3][2]24减去上方 pre[1][2]3应该得到 21但这里还要注意公式里的 pre[3][0] 是 0加回 pre[1][0] 是 0所以应该是 24-321不对这里我没减对。让我手动重新算pre[3][2] 是整个 3×2 区域和 12457827之前我上面推测 24 是错的重来。正确的前缀和表 pre[1][1]1 pre[1][2]123 pre[1][3]1236 pre[2][1]145 pre[2][2]124512 pre[2][3]12345621 pre[3][1]14712 pre[3][2]12457827 pre[3][3]45于是左上角 (2,1) 的 2×2pre[3][2]-pre[1][2]-pre[3][0]pre[1][0]27-324。和肉眼相加一致。左上角 (2,2) 的 2×2pre[3][3]-pre[1][3]-pre[3][1]pre[1][1]45-6-12128正好是 568928。最大值是 28输出 (2,2)。这个手算过程你务必自己走一遍尤其是公式里每一项对应的是哪个矩形心里要有数。4. 实际踩过的坑与排查技巧4.1 下标从0开始边界瞬间爆炸这是我见过次数最多的低级错误。有些同学一开始用 vector 开n×m二维数组并且习惯性地从下标 0 开始遍历。于是查询公式里出现pre[x-1]当 x0 时访问的是最后一行或者无效内存。有些人的解决办法是在循环里写 if 判断结果把代码搞得又臭又慢。正确做法是从设计上就规避这个问题数组多开一圈下标从 1 开始用。就像我代码里展示的那样pre[0][j] 和 pre[i][0] 都是全 0查询公式在任何边界情况下都不会产生非法下标。这个思路不仅能用在二维前缀和在差分、动态规划的棋盘型 DP 里同样适用。记住一句话能用一圈虚拟边界解决的问题就不要用 if 去硬凑。4.2 最大值初始化的选择题目并没有保证所有格子的值都是正数。一旦出现负数你把 best 初始化为 0那整个答案就是错的。比如所有格子值全是 -5c2那么所有正方形区域和都是 -20真实答案应该是左上角 (1,1)但如果你把 best 设为 0一个答案都不会被更新最后输出初始值直接送掉一次 WA。正确姿势是初始化成 long long 能表示的最小值也就是LLONG_MIN。不过这里有个小细节LLONG_MIN是极端负值参与任何运算都不会被误判放心用。如果担心老版本编译器对 climits 支持不好也可以直接写-4e18同样在 long long 范围内。总之不要用 0。4.3 严格大于和坐标更新题目要求“如果存在多个相同最大值的正方形输出最靠左上角的那个”。我们的枚举顺序是从左到右、从上到下所以第一个遇到最大值的答案一定就是最靠左上角的。为了保证这个性质更新条件必须用if (sum best)而不是if (sum best)。用的后果是后面同样等于最大值的答案会把之前记录的坐标覆盖掉最后输出的可能是右下角方向的区域这就不满足题目要求了。我见过一些学生调试半天算法没错公式没错就是错在这一个比较符号上。2025年GESP五级考试如果真出这道原题这个符号就是送分和送命的区别。4.4 存储类型与IO性能前缀和表用 int 还是 long long前面提到过这里再补一个实际后果案例。如果矩阵值最大是 10^9nm1000一个满屏正方形的和最大是 10^15远超 int 的 21 亿。在这个场景下int 不仅会溢出甚至可能是负数导致比较逻辑完全乱掉。最气人的是这不会导致数组越界或者程序崩溃只是输出一个莫名其妙的错误答案排查起来非常费劲。IO 方面输入量在 10^6 级别cin 不关同步确实有风险。我已经帮很多学生把ios::sync_with_stdio(false)加到代码里实测稳很多。如果你还是不放心直接用scanf读入也行。不要小看这种细节竞赛场上 TLE 很多时候不是算法复杂度的问题而是 IO 拖了后腿。4.5 公式背反现场推一遍最靠谱有学生总问我“二维前缀和查询公式到底是四个数怎么加减”。我的回答永远是别背画图。在草稿纸上画一个大矩形代表 pre[x2][y2]它的左边界是 1右边界是 y2上边界是 1下边界是 x2。你想在里面截出一个左上角为 (x,y)、右下角为 (x2,y2) 的小矩形。用总面积先减去上方从 (x-1,y2) 结束的大条再减去左方从 (x2,y-1) 结束的大条这时候左上角 (x-1,y-1) 那块被减了两次加回来。整个过程重复三遍公式自然就写出来了。考试的时候如果你能在一分钟内徒手推出这个公式二维前缀和这类题基本就稳了。反过来如果只会背公式一旦题目变个花样比如换成求 6 边形区域或者增加权值你就可能彻底卡住。所以我在辅导时经常让学生现场推公式不让他们直接背。5. 刷题延伸与备考建议5.1 二维前缀和的常见变式P2004 是固定正方形边长求最大和把条件改成不固定边长求整个矩阵中数值和最大的子矩形那就是另一个经典问题常见做法是把二维压成一维用最大子段和思路求解复杂度降为 O(n²·m)。GESP五级目前大概率不会考到这种动态规划等级但作为学完二维前缀和之后的下一步练习非常合适。你在洛谷搜“最大加权矩形”之类的题就能找到。另一种变式是矩阵中每个格子不是单一数值而是有颜色、高度、类型等属性要求统计满足条件的区域数量比如区域内某种颜色数量恰好是 k。这种题也是二维前缀和的衍生应用只不过在中考、高考后的计算机素养类题目里偶尔能见到影子。理解核心思路后你会觉得这些题都是一个模子刻出来的。5.2 差分数组与多维前缀和的关联二维前缀和的“亲兄弟”是二维差分。前缀和解决“多次查询子区间和”的问题差分解决“多次给子区间统一加同一个数最后一次性输出整个数组”的问题。两者的本质都是利用预处理来平衡操作代价。如果 P2004 你做得已经非常熟练我建议紧接着做一两道二维差分题比如矩阵中每次把某个子矩形区域加 k最后输出整张矩阵。这个过程能帮你把两个知识点融会贯通因为你会在里面看到一模一样的容斥公式只是方向反了过来。多维前缀和同样建立在相同逻辑上三维前缀和就是八个值之间的加减组合维数越高加减越繁复但思路的源头就是二维这个画图推出来的容斥原理。所以把二维吃透性价比极高。5.3 考场实战建议如果是真实考场上碰到这道题我的建议是先花两分钟确认 n、m、c 的范围决定用 long long 和合适数组大小再花三分钟默写前缀和模板之后处理循环边界时心里默念“左上角 x 最大只能是 n-c1”最后检查一下比较符号是不是严格大于。整套流程下来加上手算样例验证大概十到十五分钟就能拿下。平时训练时我还会做一件很多同学忽略的事AC 之后强迫自己闭卷重写一遍。第一遍照着思路写第二遍不看任何代码从零开始第三遍限制自己必须用另一种写法实现比如把cin换成scanf或者把循环里的x c - 1 n改写成x n - c 1。这种三重练习能把模板内化成肌肉记忆而不是停留在“看懂了”的层次。最后分享一个我个人的小习惯。每次给学生讲完二维前缀和我都会让他们在自己笔记本上画一遍那个“总面积减上条减左条加回重叠”的示意矩形。很多孩子嫌麻烦直接跳过但凡是认真画过的那一批后续做到矩阵 DP、树状数组时明显更稳。二维前缀和真的不是一道孤立的题它是你从“会写循环”走向“会设计算法”的第一道门槛多花半小时后面省的不止半天。