区间和
题目描述
给定一个整数数组 Array，请计算该数组在每个指定区间内元素的总和。
输入描述
- 第一行输入为整数数组 Array 的长度 n，接下来 n 行，每行一个整数，表示数组的元素。随后的输入为需要计算总和的区间下标：a，b （b > = a），直至文件结束。
输出描述
- 输出为每行一个整数，表示区间内元素的总和。
输入示例
5
1
2
3
4
5
0 1
1 3
输出示例
3
9
思路
前缀和
假设$S_i$为前$i$个元素的和，那么$S_j-S_i$就是第$i$个元素到第$j$个元素的和。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| #include <iostream>
#include <vector>
using namespace std;
int main() {
int n, a, b;
cin >> n;
vector<int> vec(n);
vector<int> p(n);
int presum = 0;
for (int i = 0; i < n; i++) {
scanf("%d", &vec[i]);
presum += vec[i];
p[i] = presum;
}
while (~scanf("%d%d", &a, &b)) {
int sum;
if (a == 0) sum = p[b];
else sum = p[b] - p[a - 1];
printf("%d\n", sum);
}
}
|
Ref
programmercarl