洛谷B3612-[深进1.例1]-求区间和-题解

题目描述

给定 个正整数组成的数列 和 个区间 ，分别求这 个区间的区间和。

输入格式

第一行包含一个正整数 ，表示序列的长度。

第二行包含 个正整数 。

第三行包含一个正整数 ，表示区间的数量。

接下来 行，每行包含两个正整数 ，满足 。

输出格式

共 行，其中第 行包含一个正整数，表示第 组答案的询问。

输入输出样例 #1

输入 #1

4
4 3 2 1
2
1 4
2 3

输出 #1

10
5

说明/提示

样例解释

第 到第 个数加起来和为 。第 个数到第 个数加起来和为 。

数据范围

对于 的数据： ；

对于 的数据： ， ​​。

思路

这题就是很简单的一维前缀和题目，先求出原数组的前缀和，然后就可以快速求出每次的区间和

代码

#include <iostream>
#include <vector>
using std::vector;
using std::cin;
using std::cout;
using std::endl;
int main()
{
	int n,m,l,r;
	cin >> n;
	//原数组
	vector<int> a(n+1,0);
	//前缀和数组
	vector<int> b(n + 1, 0);
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
		b[i] = b[i - 1] + a[i];
	}		
	cin >> m;
	for (int i = 1; i <= m; i++)
	{
		cin >> l >> r;
		cout << b[r] - b[l - 1] << endl;
	}
}