前缀和思想

何为前缀和

有一个数组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倍,前缀和不是一个模版,而是一种思想