前缀和
引入问题:给定一串序列 $a_1$,$a_2$,$a_3$,$\cdots$,$a_n$,然后 $m$ 次询问,每一次询问一段区间 $[l, r]$ 的和,答案用一个换行隔开。
$1\le n\le 10^5$。
$1\le m\le 10^5$。
方法1:每一次询问暴力枚举这一段区间,时间复杂度 $O(N\times M)$。
方法2:前缀和。定义 $s_i = s_{i-1} + a_i$,$s_0 = 0$。然后求 $[l, r]$ 这一段区间的和就是 $s_r - s_{l-1}$,具体是为什么自己想,这样时间复杂度 $O(N)$。满足条件。
在某一些特殊情况可能需要使用高精度,这里推荐在出现区间乘的时候用 $\tt{python}$,不过手打也不是不可以。
代码实现:
#include <iostream>
using namespace std;
int s[100010], a[100010];
signed main(int arg_c, char *arg_v[])
{
int n, m;
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;
}