基本思路
假设现在存在一个数组 a[1]、a[2] …… a[n],这里需要注意,前缀和下标必须是从 1 开始,因此要注意数组下标。而 s[i] = a[1] + a[2] + …… + a[n],在这里会产生如下问题
需要注意的是,前缀和并非是一个模板,更像是一个思路和数学公式,在一些问题上使用前缀和会极大的简化我们的运算。
求解 S[i] 只需一个 for 循环外加 s[i] = s[i-1] +a[i] 的递归即可,对大家来说比较简单。
s[i] 可以快速求出原数组当中一段数组的和。
将 s[0] 定义为 0 ,可以在一定程度上解决边界问题,因此一般都是从 1 开始。
题目描述
输入一个长度为 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
具体实现
代码注解
- s[i] = s[i - 1] + a[i] 是将前缀和公式初始化。
- 在数据量较多的情况下,使用 scanf 和 printf 的效率要比 cin 和 cout 快上一倍。
实现代码
#include <bits/stdc++.h> 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; } system("pause"); return 0; }