造前缀和数组

造前缀和很简单：新开一个数组 s，让每个 s[i] 等于“前一个前缀和”加上“当前这个数”。

int a[N], s[N];
s[0] = a[0];
for (int i = 1; i < n; i++)
    s[i] = s[i-1] + a[i];   // 递推：靠前一个算出当前

这样 s[i] 就是 a[0] 到 a[i] 的总和。核心是那句递推 s[i] = s[i-1] + a[i]：当前的前缀和依赖前一个 s[i-1]，所以必须从左往右按顺序算，不能跳。复杂度只有 $O(n)$，扫一遍就建好。

实战技巧：很多人喜欢让下标从 $1$ 开始，a[0] 空着、令 s[0]=0，这样

$$s_i=s_{i-1}+a_i$$

对所有 $i\ge 1$ 都成立，还能让后面“区间和 s[r]-s[l-1]”在 $l=1$ 时也不越界（s[0] 存在）。这是处理边界的常用手法。