一、算法描述
本篇文章我们来介绍一个简单的算法，前缀和。
什么是前缀和？
-
前缀和是某一个序列的前n项的和，可以理解为数学上的数列的前n项和。
-
如果 \(a\) 和 \(s\) 分别是原数组和前缀和数组，那么应该有如下关系：
s[1] = a[1];、s[2] = a[1] + a[2];、s[3] = a[1] + a[2] + a[3];
如何得到前缀和？
-
显然如果按照上面的累加法得到前缀和数组时间复杂度较大，所以我们换一个思路。
-
\(s[i]\) 表示的是前 \(i\) 项的和，那么要求前 \(i + 1\) 项的和，即 \(s[i + 1]\) ，只需要在 \(s[i]\) 的基础上加上 \(a[i + 1]\) 即可得到 \(s[i + 1]\) 了。
-
所以可以得到递推关系式：
s[i] = s[i - 1] + a[i];。
前缀和有什么作用？
-
当我们需要查询数组某段区间 \([l, r]\) 的和时，如果从 \(l\) 遍历到 \(r\) ，那么时间复杂度为 \(O(n)\) ，这个时候就可以用到前缀和的性质了。
-
\(s[r]\) 表示数组 \(a\) 的前 \(r\)项和，要求 \([l, r]\)区间内的和，只需要减去前 \(l - 1\) 项的和，即 \(s[l - 1]\) ，这样只需要 \(O(1)\)的时间复杂度就可以获取区间 \([l, r]\) 内的和。
二、题目描述
输入一个长度为 \(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 n, m;
int a[N], s[N];
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; ++i) cin >> a[i];
for (int i = 1; i <= n; ++i) s[i] = s[i - 1] + a[i];
while (m -- )
{
int l, r;
cin >> l >> r;
cout << s[r] - s[l - 1] << endl;
}
return 0;
}