题解 | #【模板】前缀和#(注释版)
【模板】前缀和
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; }