《数组》学习——区间和

题目：

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

输入描述：

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

输出描述：

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

测试用例：

输入示例

5 1 2 3 4 5 0 1 1 3

输出示例

3 9

前缀和，其思想是重复利用计算过的子数组之和，从而降低区间查询需要累加计算的次数。

测试程序：

#include <iostream> #include <vector> using namespace std; int main() { int n, a, b; std::cout << "输入整数数组的长度：" << std::endl; std::cin >> n; vector<int> vec(n); vector<int> p(n); int presum = 0; std::cout << "输入整数数组的元素：" << std::endl; for (int i = 0; i < n; i++) { std::cin >> vec[i]; presum += vec[i]; p[i] = presum; } std::cout << "输入需要计算总和的区间：" << std::endl; while (std::cin >> a>>b) { int sum; if (a == 0) sum = p[b]; else sum = p[b] - p[a - 1]; std::cout << sum << std::endl; } std::cin.get(); }