前缀和在竞赛中，往往起到优化算法的重要步骤。

前缀和的定义

定义一个合集$a$和$s$，$a$下标从$1$开始，$s_i$表示从$a_1$到$a_i$的数字之和。
合集$s$只需要$O(N)$的时间复杂度即可实现。

for (int i = 1; i <= n; i++)
    s[i] = s[i - 1] + a[i];

这里的$i$是从$1$开始的，因此$s_i$不用担心是否会越界。

前缀和的使用

已知$j≥i$且$j≤N$,$1≤i$
通过数学方法，我们可以得知以下等式
$s_j - s_i$
$=a_1 + a_2 + … + a_{j - 1} + a_j - a_1 - a_2 - … - a_{i - 1} - a_i$
$=a_j + a_{j - 1} + … + a_{i + 1}$
结果可以发现，代码s[j] - s[i]就可以得到$a_{i + 1}$到$a_j$的区间和。
那么想要求得$a_i$到$a_j$的区间和，就可以用代码s[j] - s[i - 1]得出。