前缀和

1 描述

求不修改的序列的区间和问题,可以使用前缀和思想

设:

Si=∑j=1iaj=a1+a2+⋯+ai S_i = \sum_{j=1}^i a_j = a_1 + a_2 + \cdots +a_i

所以SiS_i表示前ii个元素的累加和,称为前缀和.

可以想到

Si=Si−1+aiai=Si−Si−1 \begin{align} S_i = S_{i-1} + a_i \\ a_i = S_i - S_{i-1} \end{align}

同样,可以想到,如果想到求a3+a4+a5a_3+a_4+a_5的和,也就是区间[3,5][3,5]的区间和,只需要知道S2S_2和S5S_5即可

a3+a4+a5=S5−S2 a_3+a_4 + a_5 = S_5 - S_2

同理,区间[l,r],l⩽r[l,r],l \leqslant r的区间和就是:

∑i=lrai=Sr−Sl−1 \sum_{i=l}^r a_i = S_r - S_{l-1}

代码模板如下

int s[maxn];

int range_sum(int l,int r) {
    return s[r] - s[l-1];
}

//初始化 s数组
for (int i = 1; i <=n ; i++)
{
    cin >> s[i];
    s[i] += s[i-1];
}

from itertools import accumulate

s = [0] + list(accumulate(a))   # s[i] = 前 i 个元素的和

def range_sum(l, r):
    return s[r] - s[l - 1]

2 题目列表

3 相关题解

题目 OJ 难度
Number of Ways codeforces 1700