C++ 前缀和算法求区间和

这道题可以使用前缀和的思想来解决。

首先，我们可以计算出一个前缀和数组 prefixSum，其中 prefixSum[i] 表示前 i 个数的和。

然后，对于每个询问 (l,r)，我们可以通过 prefixSum[r] - prefixSum[l-1] 来计算出 l 到 r 的和。

下面是具体的实现步骤：

1. 读入 n 和数组 a。
2. 计算前缀和数组 prefixSum。
3. 读入 q。
4. 对于每个询问，读入 l 和 r，计算出 l 到 r 的和，并输出。

下面是代码实现：

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

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    vector<int> prefixSum(n);
    prefixSum[0] = a[0];
    for (int i = 1; i < n; i++) {
        prefixSum[i] = prefixSum[i-1] + a[i];
    }

    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        int sum = prefixSum[r-1] - (l > 1 ? prefixSum[l-2] : 0);
        cout << sum << endl;
    }

    return 0;
}

该算法的时间复杂度为 O(n+q)。