# 前缀和图解：减去共同前缀，留下区间

把两个从零开始的前缀对齐，消去共同项，理解左闭右开区间和 P[r]−P[l]；用负数、零和空区间检查边界。

原文 / Canonical: https://crazycloud.cc/learn/prefix-sum
作者: crazycloudcc
首次发布: 2026-10-16
更新: 2026-10-21

本阅读版与网页共用课程数据；互动请访问原文。

## 一句话答案

令 P[0]=0，P[k+1]=P[k]+A[k]，则 P[k] 是前 k 项的和。零起始下标的左闭右开区间 [l,r) 包含 A[l] 到 A[r−1]，其和为 P[r]−P[l]。两段前缀共有的 A[0] 到 A[l−1] 相互消去，剩下所求区间。

## 适用条件与边界

数组在查询期间保持不变；边界是整数，0≤l≤r≤n。l=r 允许空区间，和为0。本课实验为1–8个−9到9的整数预设，JavaScript整数加减精确。数学公式允许负数与零，不要求数组或前缀和有序。P有n+1项，末边界n在最后一个元素之后。

## 不变量

对每个k，P[k]恰好是A[0]到A[k−1]的和；P[0]为空和0。范围条表示项的位置与数量，不表示和的大小。

## 逐步例子

1. 数组 A=[4,−6,3,0,5,−2]，先放 P[0]=0，再依次累加得到 P=[0,4,−2,1,1,6,4]。边界k左边恰有k项，P[k]不是A[k]。
2. 查询 [2,5)：先取 P[5]=4−6+3+0+5=6。这段包含下标0到4，共5项。
3. 减去 P[2]=4−6=−2；共同的4和−6整项消去，留下3+0+5=8。所以答案是6−(−2)=8，不能把减去负数写成6−2。
4. 一般地，P[r]=(A[0]+⋯+A[l−1])+(A[l]+⋯+A[r−1])；减去 P[l] 后只剩第二组。空和定义为0，因此l=0、l=r与r=n都用同一公式。
5. [1,4) 的和是P[4]−P[1]=1−4=−3；[1,6)非空，但P[6]−P[1]=4−4=0。和为0不能反推区间为空。
6. [2,5) 的和8，向右扩成 [2,6) 后变成6，因为新加了−2。负数使前缀和与扩展区间和都不一定递增。

## 预处理、查询与更新

长度n的数组建立前缀和需O(n)时间和O(n)额外空间；每次已知l、r的查询只做一次相减，O(1)，q次查询总计O(n+q)。这些复杂度按单位成本整数算术计算，不包含动画和绘图。修改A[i]后，P[i+1]到P[n]都要相应更新，普通前缀数组最坏O(n)，不能把频繁修改也叫O(1)。任意大整数还需考虑数值表示与溢出；实验的小整数边界不代表通用输入安全。

## 常见误区

- 把r当作包含的元素：本课[l,r)不包含A[r]；闭区间下标[a,b]对应P[b+1]−P[a]。
- 混用一基和零基：题目若用一基闭区间[a,b]，转换到本课零基边界是[a−1,b)，因此答案P[b]−P[a−1]。
- 漏掉P[0]或只分配n项：P[n]是整个数组的和，必须有n+1个位置。
- 以为负数不能用前缀和：相同项消去不依赖正负；但不能随意把前缀和交给要求有序的二分查找。
- 把范围条的长度当成和：条长表示覆盖几项，下方有符号柱形才表示数值。
- 把静态求和公式当动态更新结构：交错修改和查询时需另选结构或承担重建代价。

## 自测

A=[4,−6,3,0,5,−2]。整个数组、[3,3)、[5,6)各是多少？P[1]=P[6]能推出1=6或区间为空吗？

整个数组是[0,6)，和P[6]−P[0]=4；空区间[3,3)为0；单项[5,6)为−2。P[1]=P[6]=4只说明[1,6)的和为0，这段有5项，并不为空。

## 区间应用：平均值与端点选择

1. **区间平均值也能用前缀和吗？** 可以，但区间必须非空：当 l<r 时，[l,r) 恰有 r−l 项，算术平均值为 (P[r]−P[l])/(r−l)。证明分两步：共同前缀消去给出所选项的总和，再按平均值定义除以项数。例如本课 [2,5) 包含3、0、5，和为8、项数为3，平均值是8/3；[5,6)只有−2，平均值仍是−2。上方图形、交互与同步代码仍演示区间求和；这里是在求和结果上增加一次除法的文字应用。
2. **和为0时，平均值也是0吗？** 还要看项数。[1,6)有5项，和为0，因此平均值为0/5=0；空区间[3,3)的和按约定为0，但项数也为0，0/0没有定义，平均值应标为不可用。先检查l<r，再做除法。不要截断8/3为2；需要精确表达时保留分数，浮点显示只是近似。一般大输入仍须检查前缀总和的数值范围，除法不能修复此前的整数溢出。
3. **能把两个平均值直接相减或取平均吗？** 不能普遍这样做。两个前缀的平均值使用不同分母，直接相减不会消去共同项；应先减总和，再除以区间项数。合并两个不重叠的非空区间，若项数为n₁、n₂，平均值为μ₁、μ₂，则总和分别是n₁μ₁、n₂μ₂，合并平均值为(n₁μ₁+n₂μ₂)/(n₁+n₂)。这是按项数加权，而不是通常的(μ₁+μ₂)/2。例如[2,3)平均值3、1项，[3,5)平均值5/2、2项，合并为(1×3+2×5/2)/3=8/3，而直接平均得到11/4。两段项数相等时才可普遍直接平均；空段没有平均值，只能以其总和0、项数0参与合并，且总项数必须大于0。
4. **前缀和查询是 O(1)，寻找最大区间和也是吗？** 不是。已知左右端点时只需一次相减；寻找端点还需要比较候选。设 K 为正整数、1≤r≤n，固定右边界 r，要求区间非空且长度至多 K，则合法左边界为 max(0,r−K)≤l<r。最大和等于 P[r] 减去这些候选 P[l] 的最小值，因为 P[r] 已经固定。沿用 A=[4,−6,3,0,5,−2]，取 r=3、K=3：候选前缀是0、4、−2，最大和为1−(−2)=3，对应[2,3)，不是最长的[0,3)。逐个扫描候选需 O(min(K,r)) 时间，不能把一次区间查询的 O(1) 当成寻找最优端点的总成本。
5. **为什么候选不能包含 l=r？** 因为这里要求非空。若允许 l=r，空段会给出0，可能压过所有合法负数答案。例如 A=[−4,−2]、r=2、K=2，合法候选 P[0]=0、P[1]=−4，最大和为−6−(−4)=−2；错误加入 P[2]=−6 就会得到空段的0。K=1时只能取最后一项，K≥r时可考虑从0开始的全部左边界；K=0或r=0时没有合法非空候选。遍历所有右端点的快速维护需另学单调队列等结构，本课不把它冒称已实现的交互功能。Codeforces 2261E赛后题解有带窗口约束的最小前缀应用，但还涉及括号变换，这段FAQ不是该题完整题解。

## 可选进阶：不展开，也能对拼接序列求和

先学会上面的普通区间和，再看这个额外应用。把 A=[2,−1,3] 的各个前缀依次拼起来，得到 B=[2 | 2,−1 | 2,−1,3]。竖线只分块，不是元素。AtCoder ABC480 D（2026-10-17 赛后阅读）要求在这类虚拟序列中回答区间和；N项会生成N(N+1)/2项，N=100000时超过50亿项，不能先展开。本段是文字进阶，上方交互与同步代码仍只演示普通数组求和。

沿用P[k]表示A的前k项和，再设S[0]=0、S[k]=P[1]+⋯+P[k]：第i块恰是A的前i项，所以完整k块的总和就是S[k]。完整k块有T[k]=k(k+1)/2项。对于B的前x项（0≤x≤T[N]），找到最大的k使T[k]≤x，剩下m=x−T[k]项恰是下一块的前m项，于是F(x)=S[k]+P[m]。当k=N时必有m=0，不需要访问不存在的下一块。x=0时k=m=0，F(0)=0。

例中P=[0,2,1,4]、S=[0,2,3,7]、T=[0,1,3,6]。x=5时，完整2块有3项，余下2项，因此F(5)=S[2]+P[2]=3+1=4。x=2时F(2)=S[1]+P[1]=2+2=4。B的零基左闭右开区间[2,5)包含−1、2、−1，和仍由两个前缀相减：F(5)−F(2)=0。题目的一基闭区间[L,R]则写作F(R)−F(L−1)。

先用O(N)时间和空间建立P与S，再在严格递增的T[k]上整数二分定位，每个查询O(log N)，Q次总计O(N+Q log N)；无须存储B或T数组。不能二分含负数、未必有序的P。以上按单位成本整数算术计算。题目范围内总和绝对值可达500005000000000000，超过JavaScript Number安全整数范围；应使用足够宽的整数（如C++的64位整数或JavaScript BigInt），并在乘法前选择正确类型。页面小整数实验不代表这种大输入也安全。

## 延伸学习

静态区间求和可以减去两个前缀；若任务换成批量区间加法，就在两端记录变化，最后累加还原。先区分查询与修改，再选择工具。

[继续探索：差分数组的区间加法](https://crazycloud.cc/learn/difference-array)

## 参考资料

- [Codeforces 2261E 官方赛后题解：窗口内最小前缀（进阶关联，非本课完整解法）](https://codeforces.com/blog/entry/157917)
- [AtCoder ABC480 D：Concatenation of Prefixes（2026-10-17赛后进阶）](https://atcoder.jp/contests/abc480/tasks/abc480_d)
- [AtCoder AWC0108 C：Smoothing the Temperature（历史定长区间平均值，2026-07-08）](https://atcoder.jp/contests/awc0108/tasks/awc0108_c)
- [CSES：Static Range Sum Queries（一基闭区间）](https://cses.fi/problemset/task/1646)
- [Library Checker：Static Range Sum（零基左闭右开）](https://judge.yosupo.jp/problem/static_range_sum)
- [CSES：Dynamic Range Sum Queries（适用范围对照）](https://cses.fi/problemset/task/1648)

[返回图解实验室](https://crazycloud.cc/learn)