P4759 计算区间和（基础）

解题思路

题目给出一列整数，再给出 m 个区间，每个区间用起点 L 和终点 R 表示，要求输出每个区间内所有数的和。比如 10 个数，区间 [3, 7] 就是把第 3 个数加到第 7 个数，样例中第 3 个数到第 7 个数是 3、6、4、20、15，加起来正好是 48。

最笨的办法：对每个区间，从 L 循环加到 R。但如果 n 很大、m 也很大，比如每个区间都要加 50 万个数字，一共 50 万个区间，总运算量会达到 2500 亿次，绝对超时。

解决办法还是"前缀和"。我们开一个数组 pre，pre[i] = 第 1 个数到第 i 个数的总和，在读入每个数 a[i] 的同时顺手算出来：

pre[i] = pre[i-1] + a[i]

然后任意区间 [L, R] 的和就变成一步减法：

pre[R] - pre[L-1]

可以这样理解：pre[R] 是"从头数到 R"的总和，pre[L-1] 是"从头数到 L-1"的总和，两者相减，中间 L 到 R 这一段正好被单独拎出来。就像用两把尺子比长短，一长一短，中间的差就是我们要的那一段。

题目保证 0 < L ≤ R ≤ n，所以下标不会越界。n 最多 500000，每步减法都是 O(1)，m 个区间输出 m 行，效率非常高。

注意：总和最大是 500000 × 100 = 50000000，超出 int 的范围，所以 pre 数组要用 long long，输出用 %lld。

参考代码

// 计算区间和：前缀和预处理后，O(1)求出每个区间[L,R]的和
#include <cstdio>
using namespace std;

int a[500005];          // 输入的整数序列
long long pre[500005];  // 前缀和数组，pre[i]=前i个数的和

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        pre[i] = pre[i - 1] + a[i];   // 建前缀和
    }
    for (int i = 0; i < m; i++) {
        int L, R;
        scanf("%d%d", &L, &R);
        printf("%lld\n", pre[R] - pre[L - 1]);   // 区间和 = pre[R]-pre[L-1]
    }
    return 0;
}

复杂度分析

读入并建立前缀和需要 O(n) 时间，之后每个区间只用一次减法 O(1) 就能得到答案，m 个区间共 O(m) 时间。总时间复杂度 O(n + m)，n、m 最大都是 500000，完全可以承受。空间上 pre 数组占 O(n) 个 long long。相比"每问一次就加一遍"的 O(n×m) 做法，前缀和把区间查询从"重活"变成了"秒算"，这是前缀和的经典用法。