025【模板】一维前缀和
题目描述:

1.1 算法思路:前缀和
1、先预处理出来一个【前缀和】数组——用 dp[i] 表示。
[1, i] 区间内所有元素的和,那么 dp[i - 1] 里面存的就是 [1, i - 1] 区间内所有元素的和,那么可得递推公式:dp[i] = dp[i-1] + arr[i];
2、使用前缀和数组,【快速】求出【某一个区间内】所有元素的和: 当询问的区间是 [l, r] 时:区间内所有元素的和为:dp[r] - dp[l - 1]。
1.2 算法实现
1.2.1 C++ 实现
#include <iostream>
#include <vector>
using namespace std;
int main() {
// 1、读入数据
int n, m;
cin >> n >> m;
vector<int> arr(n + 1);
for(int i = 1; i <= n; i++) cin >> arr[i];
// 2、预处理出来一个前缀和数组
vector<long long> dp(n + 1);
for(int i = 1; i <= n; i++) dp[i] = dp[i - 1] + arr[i];
// 3、使用前缀和数组
int l = 0, r = 0;
while(m--) {
cin >> l >> r;
cout << dp[r] - dp[l - ] << endl;
}
;
}













