一维前缀和
题目描述
输入一个长度为 n 的整数序列,接下来再输入 m 个询问,每个询问输入一对 l, r。
对于每个询问,输出原序列中从第 l 个数到第 r 个数的和。
输入格式
第一行包含两个整数 n 和 m。
第二行包含 n 个整数,表示整数数列。
接下来 m 行,每行包含两个整数 l 和 r,表示一个询问的区间范围。
输出格式
共 m 行,每行输出一个询问的结果。
数据范围
1≤l≤r≤n, 1≤n,m≤100000, −1000≤数列中元素的值≤1000
输入样例:
5 3
2 1 3 6 4
1 2
1 3
2 4
输出样例:
3
6
10
暴力写法
思路分析
首先给 n 和 m 存进去,接下来用数组 a[] 给 n 个数字存入,然后依次读入每个 l 和 r,
设置一个循环,再定义一个 sum 给从 l 到 r 的数值累加,最后再输出
暴力整体代码展示
#include <iostream>
using namespace std;
const int N = 100010;
int a[N];
int main(){
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++) scanf("%d", &a[i]);
for (int i = 1; i <= m; i ++){
int l, r, sum = 0;
scanf("%d%d", &l, &r);
for (int j = l; j <= r; j ++)
sum += a[j];
printf("%d\n", sum);
}
return 0;
}
但是暴力肯定是过不了的,数据范围是十万,两层循环,10 的 10 次方,大于 10 的八次方,超时
优化写法
思路分析
关于数据的存入就不在过多赘述,假设还是用 a[] 来存储每个数据,我们另开一个数组 s[],
其中 s[i] = s[i - 1] + a[i],是不是就是高中数列求前 n 项 和问题
s[r] 是前 r 项 和,s[l] 是前 l 项 和,如果我们想求 l 到 r 之间的项的和,是不是就是
s[r] - s[l] ,不是哈,看图说话
如果说 是 s[r] - s[l],通过看图,我们可以发现,这两个数值通过做差得到的结果并不是
从 l 到 r 之间的项的和,而是 从 l + 1 到 r 之间的项的和,该如何解决这个问题呢,就是往前
提一位就好了对吧,所以就是 让 s[r] 减去 s[l - 1] 就好了。
处理前缀和,就是相当于从头到尾遍历一下就好了,时间复杂度是 O(n),每次查询实践复杂度是 O(1),
平均时间复杂度化简之后就是 O(n),所以总体时间复杂度就是 O(n),ok,上代码
#include <iostream>
using namespace std;
const int N = 100010;
int a[N], s[N];
int main(){
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++) scanf("%d", &a[i]);
for (int i = 1; i <= n; i ++) s[i] = s[i - 1] + a[i];
for (int i = 1; i <= m; i ++){
int l, r;
scanf("%d%d", &l, &r);
printf("%d\n", s[r] - s[l - 1]);
}
return 0;
}