一维前缀和推荐用std::partial_sum，安全处理边界；二维需手动先每行再每列计算，注意索引偏移和缓存友好性。
一维数组前缀和：用 std::partial_sum 比手写 for 循环更安全
直接调 std::partial_sum 是最稳妥的选择，它默认做累加（std::plus），且能正确处理空数组、单元素、迭代器失效等边界。手写循环容易漏掉 prefix[0] = arr[0] 或越界访问。
- 输入必须是可随机访问的容器（
std::vector、原生数组），不能是std::list - 输出容器需预先分配空间（或用
back_inserter），否则会写入未初始化内存 - 若需原地计算（复用原数组存前缀和），确保输入输出迭代器不重叠；否则用
std::vector临时拷贝再覆盖
示例：
std::vector<int> arr = {1, 2, 3, 4};<br>std::vector<int> prefix(arr.size());<br>std::partial_sum(arr.begin(), arr.end(), prefix.begin()); // → {1, 3, 6, 10}
二维数组前缀和：别用嵌套 std::partial_sum，先按行再按列
二维前缀和不是简单套用两次 std::partial_sum 就行。标准库没有现成的二维版本，必须手动实现：先对每行做一维前缀和，再对结果矩阵的每一列做一维前缀和。顺序不能反，否则逻辑错。
- 行优先遍历保证缓存友好；列优先会导致大量 cache miss
- 注意索引偏移：二维前缀和通常定义为
sum[i][j]表示从(0,0)到(i,j)的子矩阵和，因此需预留第 0 行/列全 0，或统一用 1-based 索引 - 若原矩阵是
std::vector<:vector>></:vector>，确保每行长度一致，否则运行时崩溃
关键步骤：
// 假设 mat 是 h×w 的 vector<vector<int>>，res 初始化为 (h+1)×(w+1)<br>for (int i = 1; i <= h; ++i) {<br> for (int j = 1; j <= w; ++j) {<br> res[i][j] = mat[i-1][j-1] + res[i-1][j] + res[i][j-1] - res[i-1][j-1];<br> }<br>}
立即学习“C++免费学习笔记（深入）”；
性能陷阱：前缀和构建后查询快，但修改代价高
前缀和结构天生不支持高效单点更新。一旦数组某元素变更，一维需 O(n) 重建，二维需 O(h×w)。这不是算法缺陷，而是设计取舍——它只适合“构建一次、查询多次、几乎不修改”的场景。
- 若存在频繁更新，改用
std::vector+std::accumulate每次查区间和（O(n) 查询）；或换fenwick tree（树状数组） - 多维场景下，
std::vector<:vector>></:vector>的连续性差于一维扁平化存储；用std::vector<int> flat(h * w)</int>并手动映射坐标，能提升构建与查询局部性 - 编译器对
std::partial_sum有优化，但对自定义二维循环未必自动向量化；如需极致性能，考虑#pragma omp simd或手动展开内层循环
边界与类型：小心整数溢出和 signed/unsigned 混用
前缀和值域可能远超原数组元素类型范围。比如 vector<uint8_t></uint8_t> 有 255 个元素，前缀和最大可达 255×255=65025，超出 uint8_t 上限。
- 构建前缀和时，务必用足够宽的有符号类型（如
long long）承载累加结果，尤其在竞赛或大数据量场景 - 避免
unsigned类型参与减法运算（如二维前缀和公式中的- res[i-1][j-1]），否则可能因回绕导致巨大正数 - STL 算法如
std::partial_sum不检查溢出，也不会抛异常，结果静默错误
实际编码中，宁可显式声明：
std::vector<long long> prefix(arr.size());<br>std::partial_sum(arr.begin(), arr.end(), prefix.begin());
构建二维前缀和时最容易忽略的是内存布局与索引偏移的耦合——同一份数据，用扁平化一维数组存还是用 vector of vector 存，直接影响 cache 命中率和边界判断方式。这点在真实项目里调试起来非常隐蔽。
