# week2 note

## 前綴和程式碼
[ZJ e346: 區間和練習](https://zerojudge.tw/ShowProblem?problemid=e346)

#include <bits/stdc++.h>
using namespace std;

const int maxn = 2e5+50;
int a[maxn];
long long prefix_sum[maxn]{}; // 加{}初始化陣列為0

int main() {
    // 輸入優化
    ios::sync_with_stdio(0);
    cin.tie(0);

    // input n numbers
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }

    // deal with prefix sum
    long long sum = 0;
    for(int i = 0; i < n; i++) {
        sum += a[i];
        prefix_sum[i] = sum;
    }
    /*
    在自己電腦印出prefix_sum是一個很棒的debug方法（只限競程..)
    for(int i = 0; i < n; i++) {
        cout << prefix_sum[i] << ' ';
    }
    cout << endl;
    */

    // ask the sum in range [l, r]
    int q;
    cin >> q;
    while(q--) {
        int l, r;
        cin >> l >> r;
        l--; r--; // 轉成和陣列0-index
        if(l == 0) cout << prefix_sum[r] << '\n';
        else cout << prefix_sum[r] - prefix_sum[l-1] << '\n';
    }
}

幾點要注意的
* 要開long long，如果A序列的每個數字都是$10^9$，詢問最大的總和會是$10^9 \times 200000 > 2 \times 10^9$，超過int能儲存的範圍 [int, long long範圍](https://hackmd.io/@rDXPSsqWRemlNf_FCKoGlQ/BkanH8wrw#/0/3)
* 如果沒有特別判斷`if(l == 0)`，會有prefix_sum[-1]的狀況發生，會有問題
* 也可以改用1-index去存資料，就可以避免掉上面那個詢問到-1的問題，整個程式碼要統一就好，以下範例

    #include <bits/stdc++.h>
    using namespace std;

    const int maxn = 2e5+50;    
    long long a[maxn];

    int main() {
        // 輸入優化
        ios::sync_with_stdio(0);
        cin.tie(0);

        // input n numbers
        int n;
        cin >> n;
        for(int i = 1; i < n; i++) {
            cin >> a[i];
            a[i] += a[i-1];
        }

        // ask the sum in range [l, r]
        int q;
        cin >> q;
        while(q--) {
            int l, r;
            cin >> l >> r;
            cout << prefix_sum[r] - prefix_sum[l-1] << '\n';
        }
    }

## 如何讀去一整行含空白的字串
這次練習題的D需要讀取一整行含空白的字串

string s;
getline(cin, s);

## 陣列宣告問題
我發現很多和我初學程式碼一樣會這樣寫

int main() {
    int n;
    cin >> n;
    int a[n]; // bad
}

這樣宣告算是ub(undefined behavior)，比較建議的寫法是直接給大小

int a[2005];

陣列宣告可以宣告比需要的再大一點，避免out of bound的問題

// out of bound 範例
int a[50] = {};
int main() {
    cout << a[-1] << endl; // 
    cout << a[50] << endl; // 只能詢問到a[49]喔
}

out of bound的時候自己電腦可能還可以執行，但送到judge可能就會有問題喔。