前缀和
什么是前缀和
原数组: a[1], a[2], a[3], a[4], a[5], …, a[n]
前缀和 Si为数组的前 i项和
前缀和: S[i] = a[1] + a[2] + a[3] + … + a[i]
注意: 前缀和的下标一定要从 1开始, 避免进行下标的转换
样例
s[0] = 0
s[1] = a[1]
s[2] = a[1] + a[2]
C++ 代码
//
// Created by Owwkmidream on 2021/10/27.
//
#include "iostream"
using namespace std;
const int N = 100010;
int a[N];
int main() {
int m,n;
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
a[i]+=a[i-1];
}
int l,r;
for (int i = 0; i < m; ++i) {
cin >> l >> r;
cout << a[r]-a[l-1] << "\n";
}
return 0;
}
写的太好了
过誉,过誉