1. 思路

前缀和

2. 求解过程

3. 复杂度分析

时间复杂度:O(N) + O(q)

空间复杂度:O(N)

4. 代码

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n = 0, q = 0;
    cin >> n >> q;
    vector<int> v(n+1);
    vector<long long> dp(n+1);
    for(int i = 1;i <= n;i++)
    {
        cin >> v[i];
        // 1. 预处理前缀和数组
        dp[i] = dp[i-1] + v[i];
    }

    // 2. 使用前缀和数组
    int l = 0, r = 0;
    while(q--)
    {
        cin >> l >> r;
        cout << dp[r]-dp[l-1] << endl;
    }
    return 0;
}