普通算法——一维前缀和
一维前缀和
题目链接：https://www.acwing.com/problem/content/797/
题目描述：
- 输入一个长度为 n 的整数序列。
- 接下来再输入 m 个询问，每个询问输入一对 l,r。
- 对于每个询问，输出原序列中从第 l 个数到第 r 个数的和。
**什么是前缀和？**简单来说就是前 i 个数据的求和
前缀和有什么作用？
- 快速求某个区间中所有元素的加和。
- 例 S4 = a1 + a2 + a3 + a4; S1 = a1。所以可以通过 S4-S1 得到 a2+a3+a4 的值。
前缀和核心代码：
const int N = 1e5+10;
int sum[N], a[N]; //sum[i] = a[1] + a[2] + a[3] ..... a[i];
for(int i = 1; i <= n;i++)
{
sum[i] = sum[i - 1] + a[i];
}
#include<iostream>
using namespace std;
const int N = 100010;
int n, m, a[N], sum[N], l, r;
int main(){
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
sum[i] = sum[i - 1] + a[i];
}
while(m--){
cin >> l >> r;
cout << sum[r] - sum[l - 1] << endl;
}
return 0;
}
总结：
