筆記：【演算法新手村】[初階]筆記04 - 前綴和(一維)

題目翻譯

給定一個包含 n 個整數的陣列，你的任務是處理 q 個查詢，查詢格式為：區間 [a, b] 內數值的總和是多少？
輸入 (Input)：

• 第一行包含兩個整數 n 和 q：分別代表陣列元素的數量與查詢的次數。
• 第二行包含 n 個整數 x₁, x₂,..., xₙ：代表陣列中的各個數值。最後有 q 行描述查詢。每行包含兩個整數 a 和 b：代表要計算總和的區間範圍 [a, b]。

輸出 (Output)針對每個查詢，輸出其計算結果。

解題思路

整理上非常簡單，有甚麼問題可以直接去看 LeetCode 303. Range Sum Query - Immutable 詳解，這邊需要注意的是，他給的a跟b是口語上的用法，不懂看一下測資手動算算看應該就懂了，關於這方面的問題在 【演算法新手村】[初階]筆記04 - 前綴和(一維)中有提到一些。

注意事項

• 資料範圍：因為 n 和 q 高達 2ˣ10⁵(數值很大)，總和可能會超過32位元整數(即int)的範圍。在 C/C++ 中必須使用 long long，如果是在 Python 中則不需擔心。
• 這邊為了節省空間上的使用，直接一步到位使用sum[]進行讀入+計算，如果腦袋轉的不夠快或不熟悉的人可以先存下來再算(像之前筆記中那樣)，熟悉了之後這樣的簡單題就可以試試看一步到位。

程式碼實作 (C++)

#include <iostream>
#include <vector>

using  namespace std;

int main(){

    int n , q;
    scanf("%d %d",&n,&q);

    vector<long long> sum(n+1,0);

    int in;
    for(int i = 1 ; i < n+1 ; i++){
        scanf("%d",&in);
        sum[i] = sum[i-1]+in;
    }

    int l , r;
    while (q--)
    {
        scanf("%d %d",&l,&r);
        long long ans;
        ans = sum[r] - sum[l-1];
        printf("%lld\n",ans);
    }
    
    return 0;
}