first 题解

这道题是前缀和的经典应用。多次区间求和查询，需要将查询时间复杂度优化到O(1)。

解题思路：

1. 预处理前缀和数组 prefix[i] 表示前 i 个数的和

2. 对于询问 [l, r]，答案为 prefix[r] - prefix[l-1]

c++代码：

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    cin >> n;
    
    vector<long long> prefix(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        long long x;
        cin >> x;
        prefix[i] = prefix[i - 1] + x;
    }
    
    int m;
    cin >> m;
    
    while (m--) {
        int l, r;
        cin >> l >> r;
        cout << prefix[r] - prefix[l - 1] << '\n';
    }
    
    return 0;
}

关键点：

1. 使用 long long 存储前缀和，因为 n=100000，a_i≤10^9，总和最大为 10^14，超出 int 范围

2. prefix[0]=0 便于处理 l=1 的情况

3. 时间复杂度 O(n+m)，空间复杂度 O(n)

4. 使用快速 IO 优化输入输出

求赞