e346 - 區間和練習

🔗 前往 ZeroJudge 原題

題目描述

題目給定一個整數序列，並要求針對多個查詢，計算指定區間的總和。

解題思路

本題的核心概念是前綴和 (Prefix Sum)。首先，計算一個前綴和陣列，其中每個元素 a[i] 儲存原始陣列中從索引 0 到索引 i 的所有元素的總和。然後，對於每個查詢 [x, y]，區間 [x, y] 的總和可以通過計算 a[y] - a[x-1] 得到。這樣可以避免在每次查詢時重新計算區間總和，從而提高效率。

複雜度分析

• 時間複雜度: O(n + q)，其中 n 是陣列的長度，q 是查詢的數量。計算前綴和陣列需要 O(n) 的時間，處理每個查詢需要 O(1) 的時間，因此處理所有查詢需要 O(q) 的時間。
• 空間複雜度: O(n)，因為需要額外儲存前綴和陣列。

程式碼

#include <iostream>
using namespace std;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	long long int c,b;
	while(cin >> c){
		long long int a[c+1]={0},x,y;
		for(int i=1;i<=c;i++){
			cin >> a[i];
			if(i>1)
				a[i]+=a[i-1];
		}
		cin >> b;
		while(b--){
			cin >> x >> y;
			cout << a[y]-a[x-1] << "\n";
		}
	}
}