58. 区间和（第九期模拟笔试）

题目描述

给定一个整数数组 Array，请计算该数组在每个指定区间内元素的总和。

输入描述

第一行输入为整数数组 Array 的长度 n，接下来 n 行，每行一个整数，表示数组的元素。随后的输入为需要计算总和的区间下标：a，b （b > = a），直至文件结束。

输出描述

输出每个指定区间内元素的总和。

输入示例

5
1
2
3
4
5
0 1
1 3

输出示例

3
9

提示信息

数据范围：
0 < n <= 100000

答案：

#include<iostream>
#include<vector>using namespace std;int main()
{   int n;cin >> n;vector<int> array(n);vector<int> prefix_sum(n + 1, 0);  // 前缀和数组，长度为 n+1，prefix_sum[0] = 0for (int i = 0; i < n; i++){cin >> array[i];prefix_sum[i + 1] = prefix_sum[i] + array[i];  // 计算前缀和}int start, end;while (cin >> start >> end){// 输出区间 [start, end] 的和int sum = prefix_sum[end + 1] - prefix_sum[start];cout << sum << endl;}return 0;
}