題意#
給定一個長度為 \( n \) 的陣列，以及 \( m \) 次查詢。
每次查詢會給定區間 \( [a, b] \)，你必須回答該區間內所有元素的總和。
思路#
這是最基礎的區間和問題，
因為陣列內容不會在中途改變（靜態），
我們可以直接預處理出前綴和（Prefix Sum）陣列。
假設前綴和陣列為 v，其中 v[i] 代表前 \( i \) 個元素的總和。
當我們想知道區間 \( [a, b] \) 的總和時，
只需要計算 v[b] - v[a-1]，就能以 \( O(1) \) 的時間複雜度得到答案。
程式碼#
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
int n, m, prefix = 0;
cin >> n >> m;
// v[i] 儲存前 i 個元素的總和
vector<int> v(n + 1, 0);
for (int i = 1; i <= n; i++) {
int tmp;
cin >> tmp;
// 邊讀取邊計算前綴和
prefix += tmp;
v[i] = prefix;
}
while (m--) {
int a, b;
cin >> a >> b;
// 利用前綴和陣列，以 O(1) 回答區間和
cout << v[b] - v[a-1] << '\n';
}
}
