一维前缀和

原i  a1.a2,a3,a4,a5,a6 …. an

前缀和  Si = a1+ a2 +a3 … + ai   （注：要从下标为1开始， S0定义为0）

1、如何求Si

```c++
for (int i = 1; i <= n; I++)
    s[i] = s[i - 1] + ai;
//前i个数的和= 前i-1个数的和 + 第i个数
```

2、作用是什么

快速地求出数组[l,r]中 一段数字的和

eg：

求原数组中从l到r的和，

1、不使用前缀和的情况

循环数组去计算 ，  时间复杂度为O(n)

2、使用前缀和的情况

S[r] - S [l-1]       时间复杂度为O(1)

Sr = a1+ a2+ … a(l-1) + al + … ar

Sl-1 = a1+ a2+ … a(l-1)

3、解释

为什么要定义S0 = 0

因为如果要计算 [1,10]之间的数字之和的时候

S(10) = S(10) - S0

即就是为了使所有的情况都满足S[r] - S [l-1] 公式

4、题目：

对于每次询问，输出序列中从第i个数到第r个数的和。

输入：

第一行包含两个整数n和m。

第二行包含n个整数，表示整数数列。

接下来m行，每行包含两个整数l和r，表示一个询问的区间范围。

输出：

一共m行， 每行输出一个询问的结果。

数据范围：

1 <= l <= r <n,

1 <= n, m <= 100000

#include <iostream>

using namespace std;

const int num = 100010;
int n, m;

int a[num],s[num];

int main()
{
	// 数组中有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];//前缀和的 初始化
	while (m--)
	{
		int l, r;
		scanf("%d%d" ,&l,&r);
		printf( "%d", s[r] - s[l - 1]); //区间和的计算
	}
	return 0;

}