06区间和（前缀和） 数组

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

题目描述

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

输入描述

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

输出描述

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

输入示例

5
1
2
3
4
5
0 1
1 3

输出示例

3
9

提示信息

数据范围：
0 < n <= 100000

---

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

• 前缀和 在涉及计算区间和的问题时非常有用！

• C++ 代码 面对大量数据 读取 输出操作，最好用scanf 和 printf，耗时会小很多：

#include<bits/stdc++.h>
using namespace std;
int main(void)
{int n;cin >> n;vector<int> arr(n);int sum = 0;vector<int> pre_sum(n,0); for(int i=0;i<n;i++){cin >> arr[i];//scanf("%d", &arr[i]);sum+=arr[i];pre_sum[i] = sum;}int a,b;while(cin >> a >> b){//while(~scanf("%d %d",&a,&b)) {if(a==0){cout << pre_sum[b] << '\n';}else{cout << pre_sum[b]-pre_sum[a-1] << '\n';}}return 0;
}