前缀和与差分

前缀和与差分

前缀和；差分。

概念

前缀和预处理后，可在 O(1) 时间求任意区间 [l,r] 的和（或积、异或等可结合运算的和）。一维数组最常见：s[i]=s[i-1]+a[i]，区间和 s[r]-s[l-1]。差分是前缀和的逆操作：对原数组做区间加，只需在差分数组两端 +v、-v，再前缀还原。与 cspj.algo.dp-basic 区分：前缀和/差分是静态或离线区间统计工具，不是一般最优子结构；与 cspj.algo.enumerate-simulate 区分：有了前缀和就不应对每次查询暴力扫区间。CSP-J 复赛可能把前缀思想放在异或、模意义或「选不相交区间」的建模里。

CSP-J 常考

目前语料只有 1 道：

• cspj-r2-2025 第 3 题：复赛编程，区间异或和转化为前缀异或差，再在不重叠区间上选型。

// 一维前缀和：O(n) 预处理，O(1) 区间求和
int a[100], s[100], n;
s[0] = 0;
for (int i = 1; i <= n; ++i)
    s[i] = s[i-1] + a[i];
// [l,r] 的和（1-indexed）：
int sum = s[r] - s[l-1];

// 差分：给 [l,r] 每个数 +v
int d[100];
d[l] += v; d[r+1] -= v;
// 还原：for i: a[i]=a[i-1]+d[i]

易错点

• 下标 0 与 1：s[0]=0 是为了让 s[r]-s[l-1] 在 l=1 时成立，阅读程序 trace 时不要漏这一位。
• 前缀异或与前缀和混淆：异或满足「相同抵消」，区间异或同样是前缀异或的差。
• 差分还原时忘记对 d[r+1] 减 v，导致后缀全部被加 v。