CSES Static Range Sum Queries

解題思路

如果用最暴力的方式求區間和的話，每一次詢問的時間複雜度為 $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);