题解 | #【模板】前缀和#（注释版）

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

//本题可以用一个数组dp先把每一个原数组i下标的前所有和记录起来
//每次查询的时候就可以省去重复的计算
//所以时间复杂度为O（n+q）

int main()
{
    int n,q;
    cin>>n>>q;
    vector<int> arr(n+1);//大小为n+1是为了处理边界越界问题。
    for(int i=1;i<n+1;++i) cin>>arr[i];
    vector<long long> dp(n+1);//用一个dp数组来记录前缀和
    for(int i=1;i<n+1;i++) dp[i]=dp[i-1]+arr[i];
    int r,l;
    while(q--)
    {
        cin>>l>>r;
        cout<<dp[r]-dp[l-1]<<endl;
    }
    return 0;
}