題目鏈接：

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]);}}}