什么是前缀和

前缀和就是“从第一个数一直累加到当前位置”的和。给一个数列，它的前缀和数列记录了每个位置的累计总额。

比如数列 $2,3,5$：

• 到第 1 个：$2$
• 到第 2 个：$2+3=5$
• 到第 3 个：$2+3+5=10$

所以前缀和是 $2,5,10$，像记账本上“累计金额”那一列。

int run = 0;                       // 一路累计
for (int i = 0; i < n; i++) {
    run += a[i];                   // 加上当前数
    cout << run << " ";            // 输出到此为止的前缀和
}

用数学写，设原数列 $a_1,a_2,\dots ,a_n$，前缀和

$$s_i=a_1+a_2+\cdots +a_i=\sum _{k=1}^i{a}_k$$

它的威力在于算好之后：任意一段区间的和都能用两个前缀和相减、一步得到，不必每次从头加。这让原本 $O(n)$ 的区间求和降到 $O(1)$。下一节我们动手把这个数组造出来。