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] = 0
for (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;
}