深圳seo整站优化承接南京seo排名优化公司
何为前缀和
有一个数组a, 为
......
前缀和 =
+
+
+ ......
有两个问题:
1.如何求? 只需要从前往后遍历,令
=
+
就可以了,最开始是
=
+
,定义
= 0
2. 有什么用? 能够快速地求出原数组中某一段的和,预处理的时间复杂度是O(n),而对于每次查询时间复杂度是O(1),例如求原数组中 [l,r]区间中所有的数的和 也就是
+
+
+ ......
,如果没有前缀和数组的话,就要循环一遍才可以求出结果,他的时间复杂度是O(n),如果有前缀和数组,那么只需要
-
就能得到区间和,那么为什么是l-1,很简单,例如我们要求[1,3]区间和,也就是
+
+
, 这就是
-
的 差
3.为什么数组是从 开始,要定义
= 0 ?其实这主要是边界问题,我们要让每一个
的求值都能够用到统一的公式 ,我们求前缀和的公式是
=
+
,那么求
就要有
,我们求[1,10]的区间和是
-
,也需要
,这样就不需要额外讨论了
题目
输入一个长度为 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
代码
#include <iostream>using namespace std;const int N = 100010;
int a[N];
int S[N];
int n, m;int main(void)
{cin >> n >> m;for (int i = 1; i <= n; i++){cin >> a[i];S[i] = S[i - 1] + a[i]; // 前缀和的初始化}int l, r;while (m--){cin >> l >> r;printf("%d\n", S[r] - S[l - 1]);}return 0;
}完美运行,当然输入数据可以使用scanf,会比cin的速度快1倍,前缀和不是一个模版,而是一种思想
