解題思路#
如果用最暴力的方式求區間和的話，每一次詢問的時間複雜度為 \(O(n)\)，而因為有 \(q\) 次詢問，時間複雜度高達 \(O(nq)\)，太慢了
這時候我們就可以使用前綴和！
根據「前綴和」的章節所述，我們可以利用前綴和來每次詢問以 \(O(1)\) 的速度，加上 \(O(n)\) 的預處理求出區間和。
首先，我們先預處理前綴和：
for (int i = 1; i <= n; i++) {
psum[i] = psum[i - 1] + a[i];
}
接著，我們便可以用以下公式求出第 \(l\) 個元素到第 \(r\) 個元素的區間和。
sum = psum[r] - psum[l - 1];
常見錯誤#
long long#
其中一個可能會犯的錯誤就是使用 int 資料型態。
雖然陣列中的每一個值都在 int 的範圍內，但是區間和有機會超過 int 的範圍（約等於 \(2 \times 10^9\)）
所以，我們的 \(psum\) 陣列應該使用 long long 資料型態才能避免溢位！
減一 / 加一#
在求區間和的時候，記得要將 \(l\) 減 \(1\)，不然區間和不會包含到 \(l\) 這個數字。
因為 \(l\) 和 \(r\) 都是從 \(1\) 開始，所以不需要多做加一的動作。
完整程式碼#
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, q;
cin >> n >> q;
vector<long long> x(n + 1), psum(n + 1); // 注意，因為此程式嗎為 1-based，陣列大小要開成 n + 1
for (int i = 1; i <= n; i++) {
cin >> x[i];
psum[i] = psum[i - 1] + x[i];
}
for (int i = 1; i <= q; i++){
int a, b;
cin >> a >> b;
cout << psum[b] - psum[a - 1] << "\n";
}
}
小技巧#
C++ 裡面也有 prefix sum 的函式，其重要引入標頭檔 <numeric>。（雖然這樣沒有比較好寫）
這樣原本計算前綴和的部分可以用此程式嗎取代：
vector<long long> x(n + 1);
int psum[200005];
for (int i = 1; i <= n; i++) {
cin >> x[i];
}
partial_sum(x.begin(), x.end(), psum);
