Day12 区间和 -代码随想录 数组

代码随想录：区间和
题目链接：区间和

题目描述

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

输入描述

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

输出描述

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

输入示例
5
1
2
3
4
5
0 1
1 3

输出示例
3
9

数据范围：
0 < n <= 100000

点击查看代码

#include<iostream>
#include<vector>
#include<cstdio>
using namespace std;
int main(){int n,a,b;scanf("%d",&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(cin >> a >> b){int sum;if(a == 0) sum = p[b];else sum = p[b] - p[a-1];printf("%d\n",sum);}
}

小结

计算给定下标(含首尾)内的值总和

解题思想：通过前缀和，避免多次重复遍历计算导致超时

做法

变量

int n,a,b; //接受初始值
vector<int> vec(n); //存储n个数
int presum=0; //代表前i项之和；每遍历一个数，就加上它
vector<int> p(n); //用于存储vec前i项之和 presum 值

• 初始化vec数组，并通过presum对输入值相加，对前缀和数组p初始化
• 对每次输入值通过sum=p[b]-p[a-1]求得区间和
• 注意当a为0时，p[a-1]越界.所以当a==0时，区间和为p[b]