本讲定位：基础算法系列第 01 讲，也是整个”预处理”思想的起点。前缀和与差分是 CSP-J 复赛出现频率最高的两个技巧之一（另一个是排序），它们本身只有三四行代码，难的从来不是写，而是认出题目该用它。本讲的主线只有一句话：前缀和把”区间求和”变成 $O(1)$，差分把”区间修改”变成 $O(1)$，两者互为逆运算。
前置知识：一维/二维数组；
for循环；会读入输出。第 7 节的两道进阶题需要一点”把式子变形”的经验。适合对象：CSP-J 及以上。标注 ⭐ 的小节为进阶内容，第一遍学习可以跳过。
问题：给出长度为 $n$ 的序列 $a_1, a_2, \dots, a_n$，再给出 $m$ 个询问，每个询问给一对 $(l, r)$，要你回答 $a_l + a_{l+1} + \cdots + a_r$。数据范围 $n, m \le 10^5$。
最自然的写法是每次询问都从 $l$ 加到 $r$：
for (int i = l; i <= r; i++) ans += a[i]; // 单次询问 O(r - l + 1)
单次询问最坏要加 $n$ 次，$m$ 个询问就是 $O(nm)$。代入数据范围：$10^5 \times 10^5 = 10^{10}$ 次运算——按一秒约 $10^8$ 次估算，要跑 100 秒，稳稳超时。
卡住我们的是什么？是同一段数字被反复加了很多遍。询问 $[1, 100]$ 和询问 $[1, 101]$ 的计算过程重合了 100 项，我们却从头又算了一次。
于是有了本讲的核心思路：
预处理换查询——先花 $O(n)$ 把”所有可能重复用到的中间结果”一次性算好存起来，之后每次询问只做 $O(1)$ 的查表。总复杂度从 $O(nm)$ 降到 $O(n + m)$。
问题是：区间有 $\frac{n(n+1)}{2}$ 个（$10^5$ 时约 $5 \times 10^9$ 个），根本存不下。所以我们不存所有区间，只存 $n$ 个”从头开始”的区间——这就是前缀和。
定义 $s_i$ 为序列前 $i$ 项的和：
$$ s_i = a_1 + a_2 + \cdots + a_i, \qquad s_0 = 0 $$
$s_0 = 0$ 不是可有可无的约定，它是整个技巧成立的地基，稍后就会看到。
相邻两项只差一个数，所以不必每个 $s_i$ 都重新累加，直接递推：
$$ s_i = s_{i-1} + a_i $$