前缀和（C/C++）

目录

1. 前缀和的定义

2. 一维前缀和

2.1 计算公式

2.2 用途

         2.3 小试牛刀 

3. 二维前缀和

3.1 用途

1. 前缀和的定义

对于一个给定的数列A，他的前缀和数中 S 中 S[ i ] 表示从第一个元素到第 i 个元素的总和。

如下图：绿色区域的和就是前缀和数组中的 S [ 6 ]。

 这里你可能就会有一个疑问？为什么是 S[ 6 ] 的位置，而不是 S[ 5 ] 的位置呢？？即前缀和组中 S[ 0 ] 并没有参与求和的运算。这里先卖个关子等会在做解释。

2. 一维前缀和

2.1 计算公式

前缀和数组的每一项是可以通过原序列以递推的方式推出来的，递推公式就是：S[ i ] = S[  i - 1 ] + A[ i ]。S[  i - 1 ] 表示前 i - 1 个元素的和，在这基础上加上 A[ i ]，就得到了前 i 个元素的和 S [ i ]。

2.2 用途

一维前缀和的主要用途：求一个序列中某一段区间中所有元素的和。有如下例子：

有一个长度为 n 的整数序列。

接下来输入 m 个询问，每个询问输入一对 l，r。

对于每个询问，输出原序列中第 l 个数到第 r 个数的和。

这边是对前缀和的应用，如果用常规的方法：从 l 到 r 遍历一遍，则需要O(N)的时间复杂度。但是有前缀和数组的话，我们可以直接利用公式：sum = S[ r ] - S[ l - 1 ]，其中sum是区间中元素的总和，l 和 r 就是区间的边界。下图可帮助理解这个公式。

 当我们要求的是序列 A 的前 n 个数之和时，如果我们是从下标为 0 的位置开始存储前缀和数组，此公式：sum = S[ r ] - S[ l - 1 ] 显然就无法使用了，为了是这个公式适用于所有情况，我们将从下标为 1 的位置开始存储前缀和，并且将下标为 0 的位置初始化为 0。

 这便是为什么 S[ 0 ] 并未参与求和的运算。

有了上面的分析我们就能轻松解决这道题啦！

有一个长度为 n 的整数序列。

接下来输入 m 个询问，每个询问输入一对 l，r。

对于每个询问，输出原序列中第 l 个数到第 r 个数的和。

输入格式

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

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

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

void test01()
{
	//定义数组的大小
	const int N = 100;
	//整数序列a
	int a[N] = { 0 };
	//存储前缀和的数组s，将全部元素初始化为0，即可达到将s[0]初始化为0的目的
	int s[N] = { 0 };
	
	int n, m;
	scanf("%d %d", &n, &m);
	//整数序列的输入
	for (int i = 1; i