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

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

题目描述

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

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

输入格式

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

第二行，为 $n$ 个正整数 $a_1,a_2,?,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$

---

思路

前缀和是一种处理数组区间问题的常用方法，它可以在预处理阶段用$O(n)$的时间复杂度求出所有前缀和，然后在每次查询阶段用$O(1)$的时间复杂度求出任意一个区间的和。

首先，程序定义了两个长度为$N$的数组$a$和$s$，分别用来存储输入的序列和序列的前缀和。然后，程序读入一个整数$n$，表示序列的长度。

接着，程序进入一个循环，读入序列的每一个元素，并且在读入的同时，更新前缀和数组$s$。这里，$s[i]$的值等于$a[i]$的值加上$s[i?1]$的值，也就是说，$s[i]$的值是序列的前$i$个元素的和。

然后，程序读入一个整数$m$，表示将要进行的查询的数量。之后，程序进入一个循环，对每一个查询进行处理。每一个查询包含两个整数$l$和$r$，表示要查询的区间的起点和终点。程序通过输出$s[r]?s[l?1]$的值来得到查询的答案，这是因为$s[r]$的值是序列的前$r$个元素的和，$s[l?1]$的值是序列的前$l?1$个元素的和，所以他们的差就是序列的第$l$个元素到第$r$个元素的和。

---

AC代码

#include <iostream>
#define AUTHOR "HEX9CF"
using namespace std;

const int N = 1e7 + 7;

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

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