开始

前缀和是一种优化算法，用于求区间和。若数据范围特别大，写 for 循环很可能会爆时间复杂度，就可以用上前缀和了。前缀和有一维前缀和和二维前缀和，我暂时还没有学二位前缀和，故在此不多赘述。

使用

一维前缀和需要把一个数组比如数组 $a[1]$ 到 $a[n]$ （$n$ 为 $a$ 数组长度）储存到另一个数组中比如 数组 $b$。那么：

b[i] \ (i \le n) = \displaystyle\sum_{j = 1}^{i} a[j]

我们发现：

b[1] = a[1] \\
b[2] = a[1] + a[2] \\
b[3] = a[1] + a[2] + a[3] \\
... \\ 
b[i - 1] = a[1] + a[2] + ... + a[i - 1] \\ 
b[i] = a[1] + a[2] + ... + a[i - 1] + a[i] \\
~\\
\therefore b[i] = b[i - 1] + a[i]

这正好是一个递推的过程，$b[1] = a[1], \ b[2] = b[1] + a[2] \ …$

同时，若 $l$ 为左边界， $r$ 为又边界，$b[r] - b[l - 1] = a[r]$ 到 $a[l]$ 的区间和。

例题

前缀和模板

题目描述

给出一个数字$n$表示有个数字，

给出$n$个整数$a_1$,$a_2$,…$a_n$;

给出一个数字$m$ 有$m$个询问：
每次询问给出两个整数$s$,$e$，请求出 $a_s + a_{s+1}…a_e$

输入格式

第一行一个整数$n$

第二行$n$个整数$a_1$,$a_2$,…$a_n$;

第三行一个整数$m$

随后m行每行两个整数 s，e，($e >= s$)

输出格式

m个整数，每一个换一行

样例 #1

样例输入 #1

5
1 2 3 4 5
3
1 2
2 3
1 5

样例输出 #1

3
5
15

提示

$n <= 10^5$,$a_i <= 10^4$。

这道题目应该这样写：

#include <cstdio>
using namespace std ;

int a[100001], b[100001] ;
int n, m ;
int main()
{
	scanf("%d", &n) ;
	for(int i = 1; i <= n; i ++)
	{
		scanf("%d", &a[i]) ;
	}
	
	b[1] = a[1] ;
	for(int i = 1; i <= n; i ++)
	{
		b[i + 1] += b[i] + a[i + 1] ;
	}
	
	scanf("%d", &m) ;
	for(int i = 1; i <= m; i ++)
	{
		int s, e ;
		scanf("%d %d", &s, &e) ;
		printf("%d\n", b[e] - b[s - 1]) ;
	}
	
	return 0 ;
}