58. 区间和

题目链接：

58. 区间和

题目描述：

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

输入描述

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

输出描述

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

题目分析：

区间和问题，类似动态规划，计算出从0开始到每个位置的和，存入数组中，计算区间和时就可直接计算，使用暴力时会超时

题解：

#include<stdio.h>
int main(){int n = 0;              // 元素总和int arr[100001] = {0};  // 数组int sum[100] = {0};     // 存储0到当前位置的总和int start = 0;          // 每次开始的位置int end = 0;            // 每次结束的位置int pre = 0;            // 记录0到当前位置的和scanf("%d", &n);for(int i = 0; i < n; i++){scanf("%d", &arr[i]);pre += arr[i];sum[i] = pre;}while(scanf("%d%d", &start, &end) != EOF){if(start == 0){     // 当开始位置为0时，区间和就是sum[end]printf("%d\n", sum[end]);}else{printf("%d\n", sum[end] - sum[start-1]);}}}