一维前缀和 算法模板

S[i] = a[1] + a[2] + ... a[i]
a[l] + ... + a[r] = S[r] - S[l - 1]

解题思路

使S0 = 0是为了更方便地处理边界
S[i] = S[i-1] + a[i]

C++ 代码

#include <iostream>

using namespace std;

const int N = 100010;

int n,m;
int a[N], s[N];

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);

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

    while(m -- )
    {
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%d\n", s[r] - s[l-1]);
    }

    return 0;
}