c++中如何实现前缀和_c++数组前缀和算法实现技巧【汇总】

前缀和是手动构建的数组技巧，可将区间求和从O(n)降至O(1)，但要求数组不频繁修改；一维需构建n+1长prefix数组，定义prefix[i]为arr[0..i-1]和，查询[l,r]用prefix[r+1]-prefix[l]；二维用dpi表示左上矩形和，构建时dpi=dpi-1+dpi-dpi-1+matrixi-1，查询(r1,c1)到(r2,c2)用dpr2+1-dpr1-dpr2+1+dpr1；std::partial_sum仅适用于简单一维场景，不支持二维或自定义运算；若需频繁单点更新，应改用树状数组或线段树。

前缀和在 C++ 中不是语言内置功能，而是靠手动构建的数组技巧；它能将区间求和从 O(n) 降为 O(1)，但必须满足「数组不频繁修改」的前提。

一、一维数组前缀和：从 vector 构建 prefix 数组

核心是定义 prefix[i] 表示原数组 arr[0..i-1] 的和（即左闭右开），这样 arr[l..r] 的和就是 prefix[r+1] - prefix[l]，避免边界特判。

常见错误包括：下标越界、用 prefix[i] = prefix[i-1] + arr[i] 导致 prefix 和原数组对齐（易错配区间）。

• 推荐初始化方式：prefix[0] = 0，长度为 n+1
• 递推式必须是：prefix[i+1] = prefix[i] + arr[i]
• 查询 [l, r]（含端点）：写成 prefix[r+1] - prefix[l]，别漏 +1

vector arr = {1, 2, 3, 4, 5};
vector prefix(arr.size() + 1, 0);
for (int i = 0; i < arr.size(); ++i) {
    prefix[i + 1] = prefix[i] + arr[i];
}
// 查询 [1, 3] → arr[1]+arr[2]+arr[3] = 2+3+4 = 9
int sum = prefix[4] - prefix[1]; // prefix[3+1] - prefix[1]

二、二维数组前缀和：用 dp[i][j] 表示左上角矩形和

二维前缀和本质是容斥：以 (i,j) 为右下角的矩形和 = 左 + 上 - 左上 + 当前值。同样建议多开一行一列，让 dp[0][*] 和 dp[*][0] 全为 0。

容易踩的坑是公式记混，或在查询时没统一坐标系（比如把输入的行列当成 0-index 却按 1-index 写公式）。

• 构建时：确保 i 和 j 都从 1 开始遍历，dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + matrix[i-1][j-1]
• 查子矩阵 (r1,c1) 到 (r2,c2)（含端点，0-index 输入）：用 dp[r2+1][c2+1] - dp[r1][c2+1] - dp[r2+1][c1] + dp[r1][c1]
• 若用 vector>，注意初始化大小：行数 = 原行数+1，列数 = 原列数+1

三、前缀和 vs std::partial_sum：何时用标准库

std::partial_sum 是 C++ 标准算法，可直接生成前缀和，但它只做“就地累加”或输出到另一容器，不解决二维、不支持自定义运算（如异或前缀和）

、也不提供查询封装。

它适合快速原型或简单一维场景，但工程中常需自己封装类（如 PrefixSum1D）来绑定数据、防误用、支持 update（配合树状数组）等。

• 使用示例：partial_sum(arr.begin(), arr.end(), prefix.begin() + 1);（假设 prefix[0]==0）
• 注意：它不会自动多开一位，要自己保证目标容器足够大
• 不能替代二维逻辑——标准库无 partial_sum_2d

四、修改频繁？别硬套前缀和，考虑 std::vector + 树状数组或线段树

原始前缀和一旦构建，单点修改代价是 O(n)（得重算后面所有）。如果题目有「单点更新 + 区间查询」需求，前缀和就不适用了。

这时候应切换数据结构：树状数组（BIT）代码短、常数小；线段树更通用但稍重。二者都支持 O(log n) 更新与查询。

• 判断信号：题干出现 “update index x to value y” 或 “dynamic array” 字样
• 别试图在前缀和数组上做懒更新——没有意义，复杂度不降
• 树状数组实现只需 10 行左右，比手写带修改的前缀和更可靠

前缀和真正省事的地方，是它足够简单——几行循环 + 一次减法就能替代嵌套循环。但它的脆弱性也在这里：只要数据动了，整个加速逻辑就崩了。用之前，先盯住「改不改」这三个字。