什么是前缀和

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

举栗子

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

a151515 = {0,1,2,3,4,5,6,7,8,9,10};

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

sum151515;
sum111 = 1;
sum222 = 1 + 2;
sum333 = 1 + 2 + 3;
sum444 = 1 + 2 + 3 + 4;
sum555 = 1 + 2 + 3 + 4 + 5;

sum151515;
sum111 = a111;
sum222 = a111 + a222;
sum333 = a111 + a222 + a333;
sum444 = a111 + a222 + a333 + a444;
sum555 = a111 + a222 + a333 + a444 + a555;

计算sum数组

通过

sum111 = a111;
sum222 = a111 + a222;
sum333 = a111 + a222 + a333;

得：

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;
}