题解 | 【模板】前缀和

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

int main() 
{
    //前置工作:读入数据
    int n,q;
    cin>>n>>q;
    //大小为n+1的数组
    vector<int> arr(n+1);
    for(int i=1;i<=n;i++)
    {
        cin>>arr[i];
    }

    //采用前缀和算法
    //1.现预处理出来一个前缀和数组
    //根据数组中元素的范围，相加之和使用int是很可能由溢出情况的
    //所以这里采用long long类型数组
    vector<long long> dp(n+1);
    for(int i=1;i<=n;i++)
    {
        dp[i]=dp[i-1]+arr[i];
    }

    //2.使用前缀和数组
    int l,r;
    //询问q次
    while(q--)
    {
        cin>>l>>r;
        //使用前缀和数组求得输出结果
        cout<<dp[r]-dp[l-1]<<endl;
    }

    return 0;
   
}