什么是前缀和？如何用它 O(1) 查询区间和？

简化版

前缀和是预处理技巧:先算出「从头到每个位置的累加和」存进 prefix 数组,之后任意区间 [l, r] 的和就能 O(1) 算出来——用 prefix[r+1] - prefix[l]。预处理 O(n),之后每次查询 O(1)。适合「数组不变、多次查询区间和」的场景,把「每次查询 O(n) 累加」优化成 O(1)。

详细版

定义:prefix[i] = 数组前 i 个元素的和(a[0] + a[1] + ... + a[i-1]),约定 prefix[0] = 0。

int[] prefix = new int[n + 1];        // 长度 n+1，prefix[0]=0
for (int i = 0; i < n; i++)
    prefix[i + 1] = prefix[i] + a[i]; // 递推：前 i+1 个和 = 前 i 个和 + a[i]

// 区间 [l, r]（含两端）的和：
int rangeSum = prefix[r + 1] - prefix[l];

prefix[i+1] = prefix[i] + a[i]:一趟 O(n) 预处理。
区间和 [l, r] = prefix[r+1] - prefix[l]:两个前缀和相减,O(1)。
用长度 n+1、prefix[0]=0 的设计,能统一处理「从下标 0 开始」的区间,避免边界特判。

完整版教学

一、前缀和解决什么问题

设想一个数组固定不变,但要反复查询「某个区间的元素和」。朴素做法每次查询都从 l 累加到 r,单次 O(n),q 次查询就是 O(nq),很慢。前缀和的思路是:先花 O(n) 预处理出所有「前缀的累加和」,之后每次区间查询只需一次减法 O(1)。用「一次预处理」换来「每次查询常数时间」,是典型的空间/预处理换时间。

二、核心公式:区间和 = 两个前缀和相减

前缀和的精髓是一个减法。prefix[i] 表示「前 i 个元素的和」,那么区间 [l, r](含两端)的和就是:

sum(l..r) = (前 r+1 个的和) - (前 l 个的和) = prefix[r+1] - prefix[l]

直观理解:prefix[r+1] 包含了 a[0..r],prefix[l] 包含了 a[0..l-1],两者相减,a[0..l-1] 被抵消,剩下的正好是 a[l..r]。就像「到 r 的路程」减去「到 l-1 的路程」等于「l 到 r 的路程」。

三、为什么用 prefix[0]=0 和长度 n+1

前缀和数组的下标设计是最容易出错的地方。推荐用长度 n+1、prefix[0]=0 的定义:

prefix[0] = 0(前 0 个元素的和)。
prefix[i] = a[0] + ... + a[i-1](前 i 个)。

好处是区间公式统一为 prefix[r+1] - prefix[l],连「从下标 0 开始的区间」也不用特判(sum(0..r) = prefix[r+1] - prefix[0] = prefix[r+1])。如果用 prefix[i] = a[0]+...+a[i](长度 n)的定义,查 sum(0..r) 时要特判 l==0,容易漏。所以记住这个「偏移一位、补 0」的定式,能避开大量边界 bug。

四、走一个例子

a =      [3, 1, 4, 1, 5]
prefix = [0, 3, 4, 8, 9, 14]   （prefix[i] = 前 i 个的和）
查询区间 [1, 3]（即 a[1]+a[2]+a[3] = 1+4+1 = 6）：
  prefix[3+1] - prefix[1] = prefix[4] - prefix[1] = 9 - 3 = 6 ✓

五、适用场景与局限

适合:数组静态不变、多次查询区间和。预处理一次,查询 O(1)。
不适合:数组频繁单点修改——每次改一个元素,后面所有前缀和都要更新 O(n)。这种「既要单点改、又要区间查」的场景,用树状数组(BIT)或线段树(单点改 + 区间查都 O(log n))。
区间批量修改用它的逆运算——差分数组(见差分专题)。

前缀和、差分、树状数组是「区间操作」的一套工具,按「改什么、查什么」来选。

六、前缀和是一大类题的基础

前缀和不只是「查区间和」,更是一个思维模块,衍生出很多高频题:

和为 K 的子数组:前缀和 + 哈希表,把「找和为 k 的区间」转成「找两个差为 k 的前缀和」。
二维前缀和:O(1) 查子矩阵和。
前缀异或和:区间异或。
前缀积:除自身外的乘积。

核心都是「把区间操作转化为两个前缀量的运算」。

七、从公式证明到手算闭环

这道题成立的核心是：prefix[i] 等于原数组前 i 个元素之和，区间 [l,r] 的公共前缀恰好被相减消掉。先明确每个数组槽或哈希键的数学含义，代码中的下标偏移才不是死记硬背。

prefix[0] = 0
prefix[i + 1] = prefix[i] + a[i]
sum(l, r) = prefix[r + 1] - prefix[l]

带数字推演：数组 [2,-1,3,5] 的前缀为 [0,2,1,4,9]，所以 [1,3] 的和是 9-2=7。手算时同时列出原数组、辅助状态和本轮新增答案，能够直接发现端点偏一、初始化遗漏以及更新顺序错误。

核对维度	本题结论
正确性依据	`prefix[i]` 等于原数组前 i 个元素之和，区间 `[l,r]` 的公共前缀恰好被相减消掉
复杂度	一次扫描 O(n) 预处理，单次查询 O(1)，额外空间 O(n)
关键边界	`r+1` 是最常见的偏移错误；累计值可能超过 int；静态查询适用，频繁单点更新应换树状数组或线段树

记忆钩子：不要先背代码，先说清辅助状态“代表哪一段”；公式只是把重叠部分消掉或把边界影响传播出去。

八、实现边界与测试策略

实现时最需要警惕的是：r+1 是最常见的偏移错误；累计值可能超过 int；静态查询适用，频繁单点更新应换树状数组或线段树。这不是语法细节，而是决定算法是否仍满足题目语义的前提。

提交前应分别验证：

空数组或最小合法规模，确认哨兵位置和初始化。
查询或更新紧贴左、上边界，确认没有访问负下标。
查询或更新紧贴右、下边界，确认“终点后一位”不会越界。
包含 0、负数或重复前缀的样例，确认频次与取模语义。
大数输入，确认累计和、乘积或答案数量的整数类型足够。

如果需求从离线变成在线，或从单次恢复变成更新查询交错，原方法可能不再合适。此时应根据操作类型改用树状数组、线段树、二维结构或其他能维护动态状态的数据结构，而不是强行沿用静态前缀模型。

九、常见误区与追问

误区：前缀数组必须与原数组等长。 长度 n+1 并让 prefix[0]=0，能统一 l=0 的查询。
误区：前缀和只能处理正数。 加减法对负数同样成立，受影响的是滑动窗口的单调性。
误区：一次查询也应该先建前缀和。 只有单次查询时直接扫描可能更省空间。
追问：为什么区间和要减 prefix[l]？ 它恰好包含下标 0 到 l-1 的公共部分。
追问：原数组更新后怎么办？ 普通前缀和后缀都失效；高频更新用树状数组或线段树。
追问：怎样防止溢出？ 按最大元素与 n 估算总和上界，必要时使用 64 位整数。

十、加强记忆

前缀和是预处理:prefix[i] = 前 i 个元素和(prefix[0]=0,长度 n+1),预处理 O(n)。区间 [l,r] 的和 = prefix[r+1] - prefix[l](两前缀相减,抵消掉 a[0..l-1]),查询 O(1)。用「偏移一位补 0」的下标设计避免边界特判。适合静态数组多次区间查询;频繁单点改用树状数组/线段树,区间批量改用差分。它是「和为K子数组、二维前缀和、前缀异或」等一大类题的基础。

简化版

详细版