【AcWing算法基础】第一讲-基础算法-前缀和与差分 AcWing 795. 前缀和

摘要：
前缀和模板题。

题目

输入一个长度为 $n$ 的整数序列。
接下来再输入 $m$ 个询问，每个询问输入一对 $l$, $r$。
对于每个询问，输出原序列中从第 $l$ 个数到第 $r$ 个数的和。

输入格式
第一行包含两个整数 $n$ 和 $m$。
第二行包含 $n$ 个整数，表示整数数列。
接下来 $m$ 行，每行包含两个整数 $l$ 和 $r$，表示一个询问的区间范围。

输出格式
共 $m$ 行，每行输出一个询问的结果。

数据范围
$ 1≤l≤r≤n $,
$1≤n$, $m≤100000$,
$−1000≤$ 数列中元素的值 $≤1000$

输入样例：

5 3
2 1 3 6 4
1 2
1 3
2 4

输出样例：

3
6
10

此题考查前缀和数组的构造。对于一个给定数组alls[N]，其前缀和数组s[N]对应着对于alls[N]的每一个元素，其前缀所有元素（包括这一位）之和。
前缀和数组的应用一般伴随着一些查询操作，一个查询操作就是给定一个区间范围，让你求该范围内数的和。
另外，注意构造前缀和数组是从下标1开始构造，整体数目不变。相当于是数组下标向右偏移一位。这是因为构造前缀和数组的每一位需要依赖其前一位。当构造第1位时，需要依赖第0位。

#include <iostream>

using namespace std;
const int N = 1e5 + 10;

int main()
{
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    int alls[N];
    for (int i = 1; i <= n; i ++ ) cin >> alls[i];                  // 1
    int s[N];
    for (int i = 1; i <= n; i ++ ) {                                // 2
        s[i] = s[i - 1] + alls[i];
    }
    for (; m -- ;) {
        int l, r;
        cin >> l >> r;          
        cout << s[r] - s[l - 1] << endl;                            // 3
    }
    return 0;
}

从下标1开始读取数组，整体向右偏移一位方便查询。

从下标1开始构建前缀和数组。

查询时，s[r] - s[l]多减了一个alls[l]，所以要s[r] - s[l - 1]。

下面来思考一下预处理前缀和数组的时候，为什么 i 从 1 开始，前缀和数组第 0 位留空。

首先我们假设前缀和数组就是从第 0 位开始，即 presum[i] 对应原数组 $[0,i]$ 位元素的和。会发生什么呢？
假设求从 0 开始计算的第 4 位到第 5 位子数组和，那么使用这样一个前缀和数组可得：
int res = presum[5] - presum[4 - 1];
似乎没有问题，好，那我现在求第 0 位到第 3 位子数组的和：
int res = presum[3] - presum[0 - 1];
数组下标出现负数，为了避免这种情况，只能多一次判断，不方便。

另外，在生成前缀和数组时，递推公式为：presum[i] = presum[i - 1] + nums[i].
问题是，这个递推公式无法适配所有情况。即，当 i 取 0 时，出现异常。
为了避免这个情况，只能把 presum[0] 拿出来预设为 nums[0] ，从数组第 1 项接着按照递推公式计算。不方便。

那么，为了方便地避免以上情况，我们决定将前缀和数组相对原数组向右偏移一位，用 presum[1] 表示原数组第 0 项， presum[2] 表示原数组第 [0,1] 项之和，将 presum[i] 表示为数组中 $[0,i-1]$ 所有数之和。

那么，如果求原数组从零计第 l 项到 r 项子数组之和，那么
int res = presum[r + 1] - presum[l + 1 - 1];
因为 presum[r] 表示的是 $[0, r-1]$ 项之和， presum[l] 表示 $[0,l-1]$ 项之和。
另外，如果求原数组从1计算第 l 项到 r 项子数组之和，可以直接：
int res = presum[r] - presum[l - 1];

原题链接： AcWing 795. 前缀和