题解 | #【模板】前缀和#(注释版)

【模板】前缀和

https://www.nowcoder.com/practice/acead2f4c28c401889915da98ecdc6bf

#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;
}

全部评论

相关推荐

把球:这个听过,你加了就会发现是字节的hr
点赞 评论 收藏
分享
10-24 11:10
山西大学 Java
若梦难了:哥们,面试挂是很正常的。我大中厂终面挂,加起来快10次了,继续努力吧。
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务