1. 从洛谷 P1387 看 GESP 五级的前缀和考点
如果你刷过洛谷的普及组题单，大概率见过 P1387 这道“最大正方形”。我第一次做它的时候，看到“最大正方形”四个字，第一反应是动态规划——这是很多人的本能反应。但那次我正好在准备 GESP 五级的前缀和专题，于是强迫自己换一条路：用二维前缀和加二分答案能不能做？结果不仅做出来了，而且对二维前缀和的理解比刷十道模板题都深刻。今天这篇就完整拆解这条路，顺便把 DP 解法也放在一起对比，让你一道题同时吃透两个知识点。
这道题本身不复杂：给你一个 n 行 m 列的 0/1 矩阵，找一个最大的、全部由 1 组成的正方形，输出它的边长。GESP 五级的大纲里，前缀和属于“基础算法”的重要分支，考试中经常借这种“一眼看着像 DP”的题目来考察你对区间求和工具的理解。换句话说，如果你只会 DP 而不会前缀和，遇到考场上那道“换皮”的题可能就懵了。所以我建议你把前缀和这个解法当成主方案先掌握，DP 作为对照理解。
1.1 题目在说什么
题目输入格式不复杂：第一行两个整数 n、m，接下来 n 行每行 m 个整数，每个整数要么是 0 要么是 1。要求输出一个整数，表示矩阵中最大的、完全由 1 组成的正方形的边长。
看个简单例子：
2 3 1 1 1 1 1 0这个矩阵里，从左上角开始有一个 2×2 的全 1 方块：
1 1 1 1所以答案是 2。注意，“最大正方形”必须是正的正方形，边长相等，不能是长方形；而且正方形内不能出现任何 0，哪怕只有角落一个 0 也不行。这个限制正是后面用前缀和做可行性判断的核心。
数据范围方面，洛谷原题 n、m 通常不超过 100。这个范围其实很宽松，O(n³) 暴力都能过，但作为 GESP 五级练习，不能用“暴力能过”来安慰自己，而是要想清楚更优的做法，以及每个做法背后的适用条件。如果你去翻题解区，会发现大部分人写的是 DP，但用前缀和+二分可以做到 O(nm log min(n,m))，在 n、m 到 1000 甚至更大时依然能打，这是它最大的价值。
1.2 为什么说这是“前缀和练习”
标题里明确写着“前缀和练习”，这意味着出题者/整理者希望你在做这道题时，把重点放在前缀和这个工具上，而不是 DP。GESP 五级大纲中，前缀和经常和“区间求和”“二维矩阵操作”绑定出现，而 P1387 恰好是一个“给定矩阵，反复询问某个正方形区域内的和”的问题。
如果没有前缀和，检查一个边长为 k 的正方形是否全为 1，最朴素的做法是遍历这个正方形里的每一个格子，复杂度 O(k²)。如果要枚举所有正方形，总复杂度会飙升到 O(nm·min(n,m)²) 级别。用二维前缀和把每个区域的求和降到 O(1) 之后，我们才能用二分答案去枚举边长，否则二分本身也救不了暴力检查的复杂度。
所以这道题的正确打开方式是：先建立“二维前缀和可以快速回答子矩阵和”的直觉，再想到“正方形全为 1 等价于这个正方形区域的和等于 k²”，最后用二分把“求最大边长”转化为“判断某个边长是否可行”。三个环节一环扣一环，哪个理解不到位都容易卡壳。这也是为什么我说它是一道非常典型的前缀和综合练习题。
2. 二维前缀和：一维区间和的升级版
2.1 一维前缀和：从 O(n) 到 O(1)
在进入二维之前，先快速回顾一维前缀和。给定一个数组 a[1] 到 a[n]，我们可以预处理一个前缀和数组 s，其中 s[i] = a[1] + a[2] + ... + a[i]。这样要查询 a[l] 到 a[r] 的和，只需要计算 s[r] - s[l-1]，时间复杂度是 O(1)。
这个操作的本质是用“预处理时的加法”换“查询时的减法”。一维查询是一次减法，二维查询会变成四次加减法，因为二维比一维多了一个维度，需要处理重叠区域的容斥关系。
很多同学一上来就记二维前缀和的公式，死记硬背很容易把符号搞反。建议你先理解它的几何意义：s[i][j] 表示从矩阵左上角 (1,1) 到 (i,j) 这个矩形范围内所有数的和。如果你能把这个“矩形面积和”的图景刻在脑子里，后面的公式自己就能推出来。
2.2 二维前缀和的构造：加两次，减一次
二维前缀和的构造公式是：
pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + a[i][j];这个公式看着有点绕，其实可以这样理解：pre[i][j] 这个大矩形，等于上方的矩形 pre[i-1][j] 加上左边的矩形 pre[i][j-1]。但这两个矩形都包含了左上角那块 pre[i-1][j-1]，所以加了两次，必须减掉一次，最后再加上当前格子 a[i][j]。这就是“容斥”思想。
举一个生活化的例子：你想知道一个大长方形菜园里种了多少棵菜，可以先数上面一半，再数左面一半，但左上角那个小方块被数了两次，所以要扣掉一次，最后再加上右下角新发现的菜。二维前缀和就是把这个思路用数学公式固定下来。
代码层面，注意下标从 1 开始，pre 数组的 0 行、0 列全部初始化为 0。这样处理 i=1 或 j=1 时，pre[0][j]、pre[i][0]、pre[0][0] 都参与运算但不会越界。全局数组默认就是 0，不需要手动初始化。
2.3 任意子矩阵和：四步容斥
构建好 pre 数组之后，我们要查询从 (x1, y1) 到 (x2, y2) 这个子矩阵的和，公式是：
sum = pre[x2][y2] - pre[x1-1][y2] - pre[x2][y1-1] + pre[x1-1][y1-1];这里同样是容斥：整体大矩形 pre[x2][y2] 减去上方多出来的部分、减去左方多出来的部分，但左上角那一块被减了两次，所以要加回来。你可以类比一维：一维是一次减法，二维是两次减法加一次加法，多出来的一个维度对应多一次容斥。
以 2.1 里那个 2×3 矩阵为例，构建后 pre 的值是：
- pre[1][1] = 1
- pre[1][2] = 2
- pre[1][3] = 3
- pre[2][1] = 2
- pre[2][2] = 4
- pre[2][3] = 4
查询左上角 2×2 区域（从 (1,1) 到 (2,2)）的和，就是 pre[2][2] - pre[0][2] - pre[2][0] + pre[0][0] = 4 - 0 - 0 + 0 = 4，正好等于 2×2 全 1 的和，说明公式没问题。如果你在本地调试时不确定自己的前缀和写没写对，这就是一个非常好的手算验证方法。
3. 二分答案 + 前缀和：把求“最大”变成判“可行”
3.1 单调性是二分的基石
看到“最大正方形边长”第一反应可能是直接枚举边长，从 1 试到 min(n,m)，每试一个边长就扫描一遍矩阵。这样总复杂度大约是 O(nm·min(n,m))，在 n、m 只有 100 时能过，但数据一旦变大就吃力。更聪明的办法是二分答案，因为这个问题具备一个关键性质：单调性。
如果边长为 k 的全 1 正方形存在，那么边长小于 k 的全 1 正方形一定也存在——你只需要从那个大正方形里切出一个左上角的小正方形即可。反过来，如果边长 k 不存在，那么边长大于 k 的也一定不存在，因为更大的正方形如果存在，里面必然包含了某个 k×k 的全 1 区域。
这个“越大的越难满足”的单调性，正是二分答案可以使用的信号。我们的目标从“找最大边长 k”变成了“判断给定的 mid 是否可行”，而可行性的判断正好可以交给前缀和 O(1) 完成。二分答案把外层枚举从 O(min(n,m)) 降到了 O(log min(n,m))，效果非常明显。
3.2 check 函数怎么写
check 函数的任务很简单：判断是否存在某个边长为 len 的全 1 正方形。做法是枚举所有可能的左上角位置 (i,j)，用二维前缀和计算以它为左上角、边长为 len 的正方形区域和，然后看这个和是否等于 len×len。
如果矩阵里全是 1，区域和自然等于 len×len；只要出现一个 0，区域和就会比 len×len 小。所以等值判断就能准确区分“全 1”和“有 0”。
枚举左上角时要注意边界条件：左上角坐标 i 必须满足 i + len - 1 <= n，即正方形不能超出矩阵下边界；同理 j + len - 1 <= m，不能超出右边界。很多同学会在这里写成 i + len <= n，导致最后一行或最后一列永远枚举不到，如果最大正方形恰好贴边，答案就会偏小。这个细节后面还会再强调。
下面是 check 函数的一种实现，配合 pre 数组可以做到每次查询 O(1)：
bool check(int len) { for (int i = 1; i + len - 1 <= n; ++i) { for (int j = 1; j + len - 1 <= m; ++j) { int x2 = i + len - 1; int y2 = j + len - 1; int sum = pre[x2][y2] - pre[i-1][y2] - pre[x2][j-1] + pre[i-1][j-1]; if (sum == len * len) return true; } } return false; }这个函数在任何 len 大于 0 时都不会越界，因为 pre 数组的 0 行 0 列全是 0。如果 len 为 0，公式本身没有意义，所以我们二分时把左边界设为 1，用答案变量单独兜底处理全 0 矩阵的情况。
3.3 复杂度估算与数据范围
构建二维前缀和需要 O(nm) 的时间。二分答案的区间是 [1, min(n,m)]，所以二分次数是 O(log min(n,m))。每一次 check 都要遍历所有可能的左上角位置，数量大约是 (n - len + 1) × (m - len + 1)，最坏情况下约等于 nm 个位置，每个位置一次前缀和查询是 O(1)。所以总复杂度为 O(nm log min(n,m))。
空间上，需要一个 pre 二维数组，大小和原矩阵相同，所以空间复杂度是 O(nm)。原题 n、m 只有 100，这个复杂度看起来“杀鸡用牛刀”，但它展示了一套可以迁移到更大数据范围的通用方法。如果 n、m 都到 1000，O(nm log min(n,m)) 大概是 1000×1000×10 = 10^7 量级，依然能在常规时限内跑完；而纯暴力枚举边长加遍历正方形则是 O(nm·min(n,m)²)，这时候早就超时了。
4. 完整代码与边界细节
4.1 C++ 代码
把前面所有思路拼起来，就是下面这份完整代码。我用的是最朴素的写法，重点在于把逻辑说清楚，方便你直接照着敲。
#include <bits/stdc++.h> using namespace std; const int MAXN = 105; int a[MAXN][MAXN]; int pre[MAXN][MAXN]; int n, m; bool check(int len) { for (int i = 1; i + len - 1 <= n; ++i) { for (int j = 1; j + len - 1 <= m; ++j) { int x2 = i + len - 1; int y2 = j + len - 1; int sum = pre[x2][y2] - pre[i-1][y2] - pre[x2][j-1] + pre[i-1][j-1]; if (sum == len * len) return true; } } return false; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> m; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { cin >> a[i][j]; pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + a[i][j]; } } int l = 1, r = min(n, m), ans = 0; while (l <= r) { int mid = (l + r) / 2; if (check(mid)) { ans = mid; l = mid + 1; } else { r = mid - 1; } } cout << ans << '\n'; return 0; }我在读入 a[i][j] 的同时就顺手构建了 pre，省去一次双重循环。这样做完全没问题，但有个前提：你心里要清楚 pre[i-1][j]、pre[i][j-1]、pre[i-1][j-1] 这三个值在循环进行到 (i,j) 的时候都已经被计算过了。如果不太习惯，也可以先单独读入 a，再单独循环构建 pre，逻辑更直白，损失一点常数时间而已。
4.2 二分边界与答案初始化
二分模板我用的是闭区间写法：l=1，r=min(n,m)，while(l<=r)，mid=(l+r)/2。当 check(mid) 为真时，说明 mid 可行，但可能存在更大的边长，所以更新 ans=mid，并把左边界 l 调到 mid+1；当 check(mid) 为假时，说明 mid 太大，把右边界 r 调到 mid-1。这个模板不容易死循环，前提是你必须用心维护“左闭右闭”的区间含义。
答案变量 ans 初始化为 0，而不是 1。这是很多同学容易踩的坑：如果矩阵里一个 1 都没有，最大正方形边长应该是 0，但如果你把 ans 初始化为 1，二分结束会直接输出 1，造成错误。虽然洛谷 P1387 的原题数据不一定有这个极端情况，但 GESP 考试可能会故意放一个全 0 矩阵来卡粗心的人，养成 ans=0 的习惯更稳妥。
另一种常用的写法是把二分区间设为 [0, min(n,m)]，但 check(0) 会变成一种特殊情况，处理起来反而麻烦。我更推荐 l=1、ans=0 的组合：正常情况二分找答案，全 0 时 check(1) 直接失败，ans 保持 0，一举两得。
4.3 数组下标从 1 开始的好处
我刻意让矩阵下标从 1 开始，而不是从 0 开始。原因很简单：前缀和公式里有大量 i-1、j-1、x1-1 之类的表达式，如果矩阵下标从 0 开始，那么当 i=0 时 i-1 就会变成 -1，要么特判一堆边界，要么给 pre 数组多开一圈并偏移下标。从 1 开始的话，pre[0][j] 和 pre[i][0] 天然就是 0，所有公式无需任何分支判断，代码瞬间清爽很多。
这不是什么高深技巧，但很多人写前缀和时习惯沿用平时数组从 0 开始的做法，结果在边界处理上反复出错。我的建议是：只要题目没有强制要求从 0 读入，写前缀和相关代码一律从 1 开始。你只需要在读入时让 i、j 从 1 循环到 n、m，其他逻辑全部顺势简化。
5. 对照：动态规划如何解决同一道题
5.1 状态与转移
P1387 还有一个更经典的解法：动态规划。定义 dp[i][j] 表示以 (i,j) 为右下角的最大全 1 正方形边长。如果 a[i][j] 本身是 0，那么以它为右下角不可能形成任何全 1 正方形，所以 dp[i][j]=0。
如果 a[i][j] 是 1，情况就值得推敲了。要形成一个边长为 k 的正方形，并且右下角是 (i,j)，那么它的上方 (i-1,j) 这个位置必须能提供一个边长为 k-1 的正方形，左方 (i,j-1) 也必须能提供一个边长为 k-1 的正方形，左上角 (i-1,j-1) 同样如此。三个条件缺一不可，所以：
if (a[i][j] == 1) dp[i][j] = min(min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + 1; else dp[i][j] = 0;最终的答案就是所有 dp[i][j] 里的最大值。这个转移只需 O(1) 时间，整体复杂度是 O(nm)，比前缀和+二分还快一个 log 因子。
5.2 为什么是 min 不是 max
这是 DP 解法里最核心的问题。直观上可能会想：三个方向都取最大值再加一，不是能拼出更大的正方形吗？错。你真正需要的是三个方向同时“够用”。
用生活化的例子来说：你想在墙角放一个方形的收纳柜，它要贴着左墙、后墙和墙角。如果左墙到墙角只有 1 米，后墙到墙角有 2 米，墙角对角线区域也只有 1 米，那你能放的柜子边长只能是 1 米，而不是 2 米。因为最短的那块空间卡住了整个柜子。dp 转移里的三个方向就是这堵“左墙”“后墙”和“墙角区域”，任何一个方向不够长，整体就扩大不了。
如果写成 max，就会出现一个很隐蔽的错误：比如一个 L 形区域，横向和纵向分别都有很长的 1，但斜对角没有形成足够大的方块，max 会把不存在的正方形“脑补”出来。所以在理解 DP 解法时，一定要反复跟自己确认：正方形是二维整体，不是一维线段的叠加，必须取三个方向的短板，也就是最小值。
5.3 两种解法怎么选
我个人的看法是：如果是 GESP 五级的前缀和练习，优先写前缀和+二分。原因很直接——这道题放在“前缀和练习”标题下，训练目标就是让你熟练使用二维前缀和，你写 DP 虽然也能过，但练不到这个知识点。而且前缀和+二分的思路更通用，将来遇到“最大子矩阵”“子矩阵和等于某个值”这类问题，你会有更灵活的武器。
如果是正式比赛，且你非常确定这道题可以用 DP，那 DP 的 O(nm) 复杂度确实更优，代码也更短。但 DP 的难点在于证明转移方程，如果你对“为什么取 min”没有十足把握，比赛时可能会犹豫。相比之下，前缀和+二分几乎没有需要“顿悟”的环节，每一步都是机械而清晰的推导，更适合在时间紧张时稳定输出。
6. 实战踩坑与调试经验
6.1 前缀和公式写错的一种典型症状
二维前缀和公式最容易写错的是 pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + a[i][j] 中间的符号。有人会把减号写成加号，或者漏掉最后那个 a[i][j]。这种错误很隐蔽，因为程序不会崩溃，但输出会莫名其妙地偏大。
症状非常好认：check 函数里，明明某个正方形区域内有 0，但算出来的 sum 却等于 len×len，导致错误地判定为“可行”。根本原因是 pre 数值整体被高估，区域和也跟着虚高。排查方法也很简单：随便取一个已知的小矩阵，比如 2×2 全 1 矩阵，手算一遍 pre 应该是什么值，再打印出来对比。只要你愿意花三分钟做一次手算验证，这类错误基本能当场暴露。
6.2 二分死循环和答案偏小
二分部分最常见的两个问题，一个是死循环，一个是答案偏小。死循环通常源于更新边界时用了 r=mid 或 l=mid，而没有 +1/-1。闭区间模板里，如果 check(mid) 为真，说明答案至少是 mid，下一步要往更大的方向试探，所以 l=mid+1；如果 check(mid) 为假，说明 mid 太大了，下一步要往小方向试探，所以 r=mid-1。两边都做好 +1/-1，循环一定会在有限步内退出。
答案偏小的原因我前面提到过：枚举左上角时边界写成了 i + len <= n，而不是 i + len - 1 <= n。比如 n=4，len=3，i + len = 4 <= 4 会让 i 最大取到 1，而实际上 i 可以取 1 或 2。这个 bug 在矩阵比较小或最大正方形不贴边时很难发现，但一旦最大正方形正好贴着最后一行或最后一列，答案就会少 1。调试时可以专门构造一个“最大正方形在右下角”的测试数据，比如一个 5×5 矩阵右下角是 3×3 全 1，看看程序能不能输出 3。
6.3 对拍：用暴力验证一切
无论你写的是前缀和还是 DP，我都强烈建议在本地写一个暴力版本用来对拍。暴力思路很简单：枚举所有可能的左上角 (i,j)，再枚举边长 k，逐个格子检查正方形内是否全为 1。只要 n、m 不超过 5，这个暴力程序瞬间就能跑完。
对拍的具体流程是：写一个随机数据生成器，生成几组 n、m 都很小的 0/1 矩阵，分别跑暴力和你的优化算法，比对输出是否一致。如果结果不一致，就打印出矩阵、两个程序的输出，然后人工分析哪一步出了问题。这个方法不需要任何高深工具，但几乎能帮你解决所有隐藏 bug，尤其是前缀和这类“公式看着对但一跑就错”的情况。
6.4 GESP 考场上的一点建议
最后聊点考场上实际有用的经验。GESP 五级的前缀和题目通常不会给特别夸张的数据范围，所以你不必为了常数优化过度纠结，更重要的是把思路写清楚，降低出错率。
我一般按这个顺序做题：先把题意完全读懂，确定输入输出格式；然后看数据范围，如果 n、m 很小，可以先在草稿纸上想清楚暴力解法，确保自己对题意理解正确；再往优化方向想，看能不能用前缀和或者 DP。P1387 这种题，关键词“矩阵”“全 1”“正方形”出现时，应该立刻在脑子里弹出两个候选方案：前缀和+二分、DP。你可以都推一遍，选自己最有把握的那个写。写完之后不要立刻提交，先拿手算样例走一遍流程，确认输出符合预期，再交上去。
另一个容易被忽视的点是读入优化。虽然 n、m 不影响大局，但加上 ios::sync_with_stdio(false) 和 cin.tie(nullptr) 是一个好习惯，避免某些测试点数据偏大时 cin 成为瓶颈。如果考试环境实在不允许用 bits/stdc++.h，就把头文件换成标准的 iostream、algorithm 等，核心代码不用变。做完之后，我习惯再用全 0 矩阵和全 1 矩阵各测一次，前者应该输出 0，后者应该输出 min(n,m)，这两个极端情况能过滤掉大部分边界错误。
