P4766 连环询问（入门）

解题思路

题目说得很直白：给定 n 个正整数，接下来有 m 次询问，每次问一个区间 [L,R] 里所有数的和，要我们把每次的答案都输出。这种"反复问区间和"的题目，就是前缀和最经典的应用场景。可以分几步想清楚：

1. 第一步，想一想为什么不能每次从头加。 如果每次询问都把区间里的数从头加一遍，当区间很长、询问又很多时，就会重复计算很多次，非常浪费。举个例子：第一次问 [1, n]，第二次问 [2, n]，光第一个数就被算了两次。再想想极端情况：10 万个数、10 万次询问，每次平均要加 5 万个数字，一共就是 50 亿次操作，肯定超时。

2. 第二步，用前缀和"提前准备好答案的原材料"。 思路是：先扫描一遍数组，把 prefix[i] 记成"前 i 个数的总和"。之后任何一次询问 [L,R]，答案立刻就是 prefix[R] - prefix[L-1]，不管区间多长都只要一次减法。为什么这样减就对？prefix[R] 是前 R 个数的总和，prefix[L-1] 是前 L-1 个数的总和，两者一减，正好把第 L 个到第 R 个之间的数留下来。这就像提前把每段路的路程都写在路牌上，别人问路，查一下两个路牌之差就行了。

3. 第三步，按顺序写代码。 输入格式是先 n、m，再 n 个数，最后 m 组询问，每组一行 L、R，别把顺序读反了。先读入 n 和 m，然后读入 n 个数，边读边累加出 prefix；接下来循环 m 次，每次读入 L、R，用公式算答案并输出一行。注意下标从 1 开始，prefix[0] 初始为 0。

4. 第四步，用样例验证。 n=4，数字 4 3 2 1，prefix 依次是 4 7 9 10。第一次问 [1,4]：prefix[4]-prefix[0]=10；第二次问 [2,3]：prefix[3]-prefix[1]=9-4=5。输出 10 和 5，完全正确。

5. 第五步，留意边界和数组大小。 题目保证 1≤L≤R≤n，所以 prefix[L-1] 最小是 prefix[0]，不会出现越界读负下标的问题；但要确保数组大小开够，n 比较大的时候 prefix 要开到 500005，并且用 long long 存前缀和。

6. 第六步，想想特殊询问。 如果问的区间只有一个数 L=R，公式算出来就是那个数本身，不会出错；如果问的是整个数组 [1,n]，算出来就是所有数字之和。m 最大也能到 500000，输出的行很多，用 一行一行输出即可。

参考代码

// 连环询问：回答 m 个区间 [L,R] 中所有正整数的和，用前缀和快速回答
#include <iostream>
int main() {
    int n, m;
    std::cin >> n >> m;
    long long prefix[500005] = {0}; // prefix[i] 表示前 i 个数字的和
    for (int i = 1; i <= n; ++i) {
        long long num;
        std::cin >> num;
        prefix[i] = prefix[i - 1] + num;
    }
    while (m--) {
        int L, R;
        std::cin >> L >> R;
        std::cout << prefix[R] - prefix[L - 1] << '\n'; // 区间和 = 前R个的和 - 前L-1个的和
    }
    return 0;
}

复杂度分析

建立前缀和数组需要 O(n) 时间，回答 m 次询问每次 O(1)，总时间复杂度 O(n+m)，空间复杂度 O(n)。如果不用前缀和、每次询问从头加，最坏情况是 O(n*m)，会超时；用了前缀和之后，即使 n、m 都是 500000，也就 100 万次操作，瞬间出结果。这就是"预处理换时间"的思想，也是前缀和最重要的用处。