洛谷P8218 【深进1.例1】求区间和（前缀和）

题目传送门
题目难度：普及一

【深进1.例1】求区间和

题目描述

给定 $n$ 个正整数组成的数列 $a_1,a_2,\cdots ,a_n$ 和 $m$ 个区间 $[l_i,r_i]$，分别求这 $m$ 个区间的区间和。

对于所有测试数据，$n,m\le 10^5,a_i\le 10^4$

输入格式

第一行，为一个正整数 $n$ 。

第二行，为 $n$ 个正整数 $a_1,a_2,\cdots ,a_n$

第三行，为一个正整数 $m$ 。

接下来 $m$ 行，每行为两个正整数 $l_i,r_i$ ，满足$1\le l_i\le r_i\le n$

输出格式

共 $m$ 行。

第 $i$ 行为第 $i$ 组答案的询问。

样例 #1

样例输入 #1

4
4 3 2 1
2
1 4
2 3

样例输出 #1

10
5

提示

样例解释：第 $1$ 到第 $4$ 个数加起来和为 $10$。第 $2$ 个数到第 $3$ 个数加起来和为 $5$。

对于 $50\%$ 的数据：$n,m\le 1000$；

对于 $100\%$ 的数据：$1\le n,m\le 10^5$，$1\le a_i\le 10^4$

题目分析：本题是一道简单题，需要用到前缀和的模板，下面介绍下前缀和。

前缀和：从名字上看，我们就大概能知道算法的作用。前缀，就是某位置之前的所有数，为该数的前缀，前缀和，就是对该位置前缀的元素进行求和。

一维前缀和
前缀和的模板其实非常简单，它更像是一种思想。前缀和思想可以快速地解决问题，看个例子：
假如给定一段序列，需要你求出 [l,r]区间的和，该如何求？最简单的方式就是通过 for 循环遍历一遍，时间复杂度为 O(N)而 前缀和算法 ，在O(1)的时间复杂度完成。

算法步骤：前缀和算法主要分为两步，预处理 和 查询 ：假设 a,s 分别为 原数组 和 前缀和数组。

**预处理 ：**预处理就是求 前缀和数组 。对于前缀和数组 s，其中元素满足 S[i]=a[1]+a[2]+a[3]…a[i] 求前缀和时，下标从 1 开始。大体过程如下：

for (int i = 1; i <= n; i++) {
        s[i] = s[i - 1] + a[i];
    }

前缀和数组每项 s[i] 是它的前一项 s[i−1] 加上原数组 a[i] 因为前缀和数组的前一项 s[i−1]，是 a 数组中前 i−1 项的值嘛，所以求 s[i] 时只上 a[i] 就可以计算出来前 i项的前缀和了。
查询：
查询就是求给定区间 [l,r] 的值。现在由于求出了前缀和数组，那么查询时只要一步 S[r]−S[l−1]，就可以求出结果。

最后就是代码部分：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;

int s[N],a[N];
int n,m;

ll read()
{
	ll s=0,f=1;
	char ch=getchar();
	
	while (ch<'0'||ch>'9')
	{
   	   if (ch=='-') f=-1;
	   ch=getchar();
	}
	while (ch>='0'&&ch<='9')
	{
	   s=s*10+ch-'0';
	   ch=getchar();
	}
	return s*f;
}

int main() {
   
    n = read();
    
    s[0] = 0;
    
    for(int i = 1; i <= n; i++) 
    {
    	a[i] = read();
    	s[i] = s[i - 1] + a[i];
	}
	
	m = read();
	
	while(m--)
	{
		int l = read(),r = read();
		cout<<s[r] - s[l-1]<<endl; 
	}
	
    return 0;
}