前缀和

一维前缀和

算法思想

一维前缀和的思想就是我第 $i$ 下标的数组格子里放的是 $0 \sim i$ 所有格子的和，包含 $i$，这一步就是预处理，预处理帮我们解决不用每次找到要相加元素，一个一个加起来，这种方法效率太慢了，所以我们利用

就可以得到 $i \sim j$ 格子的和。不管我们需要哪两个下标之间的值，我们总能快速的求出（只需要减一下就可以）。

步骤

1. 预处理，这一步就是前缀和的思想。在脑中思考一下，任意选取一个元素 $i$。这个元素之前的j一定满足 $0\sim j$ 之间所有格子的和, 所以我们任选取的元素怎么预处理值，显然，$s[i - 1] + x$.
2. 我们已经预处理完，现在数组一定满足任意 $s[i]$ 都是预处理前 0~i 之间的和，求的是某两个元素中间所有元素的和，所以根据面积原理: $(s1 + s2) - s1 = s2$ ，得到 $s2$ 之间的值。

代码实现¹

#include <iostream>

using namespace std;

const int N = 1e5 + 9;
int a[N], s[N];

int main()
{
    int n, m;
    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;
}