題目

給定一個整數數組 Array，請計算該數組在每個指定區間內元素的總和。

• 輸入：
  1. 第一行輸入：為整數數組 Array 的長度 n，
  2. 接下來 n 行，每行一個整數，表示數組的元素。
  3. 隨后的輸入為需要計算總和的區間，直至文件結束。
• 輸出：
  • 輸出每個指定區間內元素的總和。

思路 & 代碼

前綴和

統計 vec[i] 數組上的區間和

• vec[i]：數組；
• p[i]：下標 0 到 i 的 vec[i] 累加 之和
• 若要統計 vec 數組上 下標 2 到 5 之間的累加和：p[5] - p[1]

p[1] = vec[0] + vec[1];

p[5] = vec[0] + vec[1] + vec[2] + vec[3] + vec[4] + vec[5];

p[5] - p[1] = vec[2] + vec[3] + vec[4] + vec[5];

#include <iostream>
#include <vector>
using namespace std;int main(){int n, a, b;cin >> n;vector<int> nums(n);vector<int> pre(n);int presum = 0;for(int i = 0; i < n; i++){scanf("%d",&nums[i]);presum += nums[i];pre[i] = presum;}while(scanf("%d%d", &a, &b) == 2) {int sum;if(a == 0){sum = pre[b];}else{sum = pre[b] - pre[a - 1];}printf("%d\n",sum);}
}

總結

• 輸入一個元素：scanf(“%d”,&a);
• 輸入二個元素：scanf(“%d%d”, &a, &b);
• 打印：printf(“%d\n”,sum);