C++ 前缀和算法解决区间和问题

这道题可以使用前缀和的思想来解决。首先，我们可以预处理出一个前缀和数组'prefixSum'，其中'prefixSum'[i]表示前i个数的和。然后，对于每一个询问(l, r)，我们可以通过'prefixSum'[r]-prefixSum'[l-1]来计算出[l, r]区间的和。

具体的实现步骤如下：

首先读入n个数，并计算出前缀和数组'prefixSum'。
循环处理q个询问：
- 读入询问的左右边界l和r。
- 计算[l, r]区间的和'sum'，即'sum' = 'prefixSum'[r] - 'prefixSum'[l-1]。
- 输出'sum'。

代码如下：

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

int main() {
    int n;
    cin >> n;
    vector<int> nums(n + 1);
    vector<int> prefixSum(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> nums[i];
        prefixSum[i] = prefixSum[i - 1] + nums[i];
    }

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

    return 0;
}

这个算法的时间复杂度是O(n + q)，其中n是数组的长度，q是询问的个数。空间复杂度是O(n)，用来存储前缀和数组。