住宿统计c++TLE求解

Question

描述
国庆节提倡就地过节，想出去玩的国庆一下子闲下来了。
没事找事的国庆，翻看着爸爸所在宾馆的住宿信息，突发奇想，已知每天宾馆的住宿人数，我能否快速的统计出从第 a 天到第 b 天的住宿人数呢？
作为国庆的同学，你能给出一个非常快速的统计方案吗？
输入描述
第一行，两个数 M 和 N，其中 M 是天数，N 是查询次数。
第二行，N 个正整数，表示每天的住宿人数。
以下 N 行，每行两个正整数a，b。
输出描述
N 行，每行一个正整数，表示从 a 天到 b 天，住宿的总人数。
样例输入 1
5 3
1 2 3 4 5
1 5
4 5
2 4
样例输出 1
15
9
9
提示
对于 100% 的数据：每天入住人数<=100; a<=b。
对于 40% 的数据：n,m<=1000；
对于 100% 的数据：n,m<=100000。

Answer 1

引自免费微信小程序：皆我百晓生

为了解决这个问题，我们可以使用前缀和数组（prefix sum array）来优化计算过程。前缀和数组可以让我们在常数时间内获取任意一段区间内的元素之和，这将大大提高我们的效率。

以下是使用C++实现的代码：

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int M, N;
    cin >> M >> N;

    vector<int> daily_guests(M);
    for (int i = 0; i < M; ++i) {
        cin >> daily_guests[i];
    }

    // 计算前缀和
    vector<int> prefix_sum(M + 1, 0);
    for (int i = 0; i < M; ++i) {
        prefix_sum[i + 1] = prefix_sum[i] + daily_guests[i];
    }

    // 查询
    for (int i = 0; i < N; ++i) {
        int a, b;
        cin >> a >> b;
        cout << prefix_sum[b] - prefix_sum[a - 1] << endl;
    }

    return 0;
}

这段代码首先读取天数M、查询次数N以及每天的住宿人数daily_guests。然后，它创建了一个名为prefix_sum的前缀和数组，用于存储从第一天到每一天的累计住宿人数。接着，代码遍历查询，每次查询时只需在前缀和数组中找到对应的区间和即可，时间复杂度是O(1)，因此整体的时间复杂度为O(N)，满足题目要求。

为了更好地理解这个算法，这里是一个简单的示例解释：

• 假设我们有5天的数据: daily_guests = [1, 2, 3, 4, 5]
• 前缀和数组会是: prefix_sum = [0, 1, 3, 6, 10, 15]
• 对于查询 (1, 5)，我们需要的是prefix_sum[5] - prefix_sum[0] = 15 - 0 = 15
• 对于查询 (4, 5)，我们需要的是prefix_sum[5] - prefix_sum[3] = 15 - 6 = 9
• 对于查询 (2, 4)，我们需要的是prefix_sum[4] - prefix_sum[1] = 10 - 3 = 7

这样，我们就得到了正确的答案。