什么是前缀和

一个数组sum 的第i个元素 = 数组a的第一个元素到第i个元素之和

举栗子

定义一个数组a(不取索引为0的元素)

a[15] = {0,1,2,3,4,5,6,7,8,9,10};

定义一个数组sum 为数组a的前缀和数组

sum[15];
sum[1] = 1;
sum[2] = 1 + 2;
sum[3] = 1 + 2 + 3;
sum[4] = 1 + 2 + 3 + 4;
sum[5] = 1 + 2 + 3 + 4 + 5;

sum[15];
sum[1] = a[1];
sum[2] = a[1] + a[2];
sum[3] = a[1] + a[2] + a[3];
sum[4] = a[1] + a[2] + a[3] + a[4];
sum[5] = a[1] + a[2] + a[3] + a[4] + a[5];

计算sum数组

通过

sum[1] = a[1];
sum[2] = a[1] + a[2];
sum[3] = a[1] + a[2] + a[3];

得：

sum[1] = a[1]
sum[2] = sum[1] + a[2];
sum[3] = sum[2] + a[3]

综上 sum[i] = sum[i - 1] + a[i];

通过前缀和求区间的和

例如 我们需要求索引l~r区间内(包括l,r)的元素之和

若 l = 2 , r = 4：

和 = a[2] + a[3] + a[4]
∵

sum[1] = a[1];
sum[2] = a[1] + a[2];
sum[3] = a[1] + a[2] + a[3];
sum[4] = a[1] + a[2] + a[3] + a[4];

在以上内容中 a[2] + a[3] + a[4] = (a[1] + a[2] + a[3] + a[4]) - a[1] = a[2] + a[3] + a[4] = sum[4] - sum[1]
∴和 = sum[4] - sum[1]

若 l = 3 , r = 5：

和 = a[3] + a[4] + a[5]
∵

sum[1] = a[1];
sum[2] = a[1] + a[2];
sum[3] = a[1] + a[2] + a[3];
sum[4] = a[1] + a[2] + a[3] + a[4];
sum[5] = a[1] + a[2] + a[3] + a[4] + a[5];

在以上内容中 a[3] + a[4] + a[5] = (a[1] + a[2] + a[3] + a[4] + a[5]) -(a[1] + a[2]) = sum[5] - sum[2]
∴和 = sum[5] - sum[2]

综上 索引l~r区间内(包括l,r)的元素之和 = sum[r] - sum[l - 1]

例题

AC代码

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int a[100005] , sum [100005];
    sum[0] = 0;
    int n , l , r;
    cin >> n ;

    for(int i = 1 ; i <= n ; i ++)
    {
        cin >> a[i];
        sum[i] = sum[i - 1] + a[i];
    }
    while (cin >> l >> r)
        cout << sum[r] - sum[l - 1];
    return 0;
}