11.前缀和

前缀和里，下标从1开始。

原数组为a[1]，a[2]，a[3]，...，a[n]。

前缀和数组s[i]表示原数组中前i个数的和。s[i] = a[1] + a[2] + ... + a[i]。

前缀和数组是由原数组计算出来的。

1：如何求s[i]:

　　从前往后递推一遍就好了

　　s[0] = 0

2：前缀和数组的作用：

　　快速求出原数组某一段的和

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int a[N], s[N];
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        s[i] = s[i - 1] + a[i];
    }
    while (m--) {
        int l, r;
        cin >> l >> r;
        cout << s[r] - s[l - 1] << endl;
    }
    return 0;
}