P4762 物资准备（入门）

解题思路

新型火炮要攻打防线上的据点，每个据点有一个牢固值，比如牢固值是 10，就需要 10 发炮弹才能摧毁。一共有 m 门火炮，每门火炮负责摧毁一段连续范围的据点，而且它们发射前没有沟通，所以不同火炮打的区间可能有重叠，会造成炮弹浪费。题目要我们算出：一共需要准备多少发炮弹。

其实答案就是所有区间的牢固值之和相加。因为每门火炮打 [L,R]，就需要这一段的牢固值总和那么多发炮弹，把 m 门火炮需要的炮弹数加起来就是总数。

如果对每个区间都从头加一遍，n 和 m 都到 100000 时就会超时。我们还是用前缀和：pre[i] 表示前 i 个据点的牢固值之和，区间 [L,R] 的牢固值总和就是 pre[R] - pre[L-1]，O(1) 就能算出来。把每次算出的区间和累加进 ans 变量，最后输出 ans。

样例验证：7 个据点牢固值 2 10 5 3 6 4 9。第 1 门炮打 3~5，需要 5+3+6=14 发；第 2 门炮打 6~7，需要 4+9=13 发；合计 14+13=27，和样例输出一致。

这里有一个容易忽视的坑：答案不是把所有据点的牢固值加一遍，而是把每个区间分别算好再相加，因为区间会重叠，同一个据点可能被多门炮重复攻打。另外，m 次区间和累加起来可能非常大，所以 ans 和 pre 都要用 long long 来存。

参考代码

// 求所有火炮摧毁范围内牢固值总和（即炮弹总数）：前缀和累加每个区间
#include <iostream>
int main() {
    int n, m;
    std::cin >> n >> m;
    long long pre[100005] = {0}; // pre[i] 表示前 i 个据点的牢固值之和
    for (int i = 1; i <= n; ++i) {
        long long x;
        std::cin >> x;
        pre[i] = pre[i - 1] + x;
    }
    long long ans = 0;
    for (int i = 0; i < m; ++i) {
        int L, R;
        std::cin >> L >> R;
        ans += pre[R] - pre[L - 1]; // 把每轮需要的炮弹累加进答案
    }
    std::cout << ans << '\n';
    return 0;
}

复杂度分析

建立前缀和数组需要 O(n) 时间，处理 m 个区间每个只需要 O(1) 的减法并累加，所以总时间复杂度是 O(n+m)，空间复杂度是 O(n)（一个 pre 数组）。n、m 最大都是 100000，总共约 20 万次操作，1 秒内绰绰有余。如果不做前缀和、每个区间从头加，最坏会有 100000×100000=100 亿次运算，会严重超时。