一维前缀和定义为prefix[i] = arr[0]+...+arr[i-1]以避免查询[l,r]时边界特判；二维前缀和标准查询式为prefixr2+1-prefixr1-prefixr2+1+prefixr1；动态更新需改用树状数组或线段树。

一维前缀和：为什么 prefix[i] 要定义为 arr[0] + ... + arr[i-1]？

因为这样能让查询 [l, r] 区间和写成 prefix[r+1] - prefix[l]，完全避开边界特判。如果定义成包含 arr[i]，每次查询就得判断 l==0，多一次分支，对高频查询有可观开销。

实操建议：

• 初始化时用 vector<long long> prefix(n + 1)</long>，避免 int 溢出
• 构建用单次遍历：for (int i = 1; i
• 查询函数封装为内联：inline long long range_sum(int l, int r) { return prefix[r+1] - prefix[l]; }
• 别在循环里反复调用 prefix.size()，存到局部变量里

二维前缀和：prefix[i][j] 的递推式为什么是 prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1] + mat[i-1][j-1]？

这是容斥原理的直接体现：上边 + 左边会把左上角重复加一次，必须减掉。错写成 + prefix[i-1][j-1] 或漏减，会导致所有查询结果偏大。

常见错误现象：

• 查询 [r1,c1] 到 [r2,c2] 时，返回负数或远超预期值 → 检查是否用了 mat[i][j] 而不是 mat[i-1][j-1] 初始化
• 越界访问 prefix[-1][*] → 确保 prefix 是 (m+1) × (n+1) 大小，索引从 1 开始
• 使用 int 存储导致中间值溢出 → 建议全用 long long，尤其当矩阵元素绝对值 > 1e4 且尺寸 > 1e3

标准查询式：prefix[r2+1][c2+1] - prefix[r1][c2+1] - prefix[r2+1][c1] + prefix[r1][c1]

C++ Code Review Master

组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。

下载

动态更新场景下，还能用前缀和吗？

不能。原始前缀和是静态结构，单点修改需 O(n) 或 O(n²) 重构整个数组。此时应切换数据结构：

• 一维：改用 fenwick_tree（树状数组）或 segment_tree，单点更新 + 区间查询均为 O(log n)
• 二维：可用二维树状数组（注意内存布局连续性），或降维为一维后套用；不推荐二维线段树——常数太大，且实现易错
• 若更新极少（比如预处理后只查不改），仍用前缀和更省空间、更快；别为了“可能更新”提前引入复杂度

一个典型误判：看到题目说“支持修改”，就立刻放弃前缀和。先数清修改次数 —— 若 q_update ，离线处理 + 重建前缀和反而更快。

性能陷阱：缓存友好性比公式简洁更重要

二维前缀和遍历时，必须按行优先顺序填充 prefix[i][j]（即外层 i，内层 j）。若反过来，CPU 缓存行失效频繁，实测在 2000×2000 矩阵上慢 3–5 倍。

实操细节：

• 用 vector<vector long>></vector> 时，确保每行内存连续；不要用指针数组模拟二维
• 若矩阵很大（> 100MB），考虑用一维数组模拟二维：prefix[i * (n+1) + j]，并手动计算索引
• 编译加 -O2 后，编译器能优化掉部分边界检查，但不会自动重排循环顺序 —— 这个必须手写对

真正卡时间的往往不是公式推导，而是内存访问模式没对齐 CPU cache line。

C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！