【C++】競程筆記（前綴和、差分 習題練習）

1. Zerojudge e346. 區間和練習：https://zerojudge.tw/ShowProblem?problemid=e346

:::info
內容：
給定一個長度為 $n$ 的整數序列 $A$ ，請回答 $q$ 筆詢問。每筆詢問會問其中一段連續區間的總和為何。

輸入說明：

• 輸入的第一行有一個整數 $n$ ( $1 \leq n \leq 200000$ )，代表 $A$ 序列的長度。
• 第二行有 $n$ 個整數以空白分隔，依序表示 $A$ 序列中的數字，其中數字的絕對值不會超過 $10^{9}$ 。
• 第三行有一個整數 $q$ ( $1 \leq q \leq 200000$ )，代表詢問的數量。
• 接下來有 $q$ 行，每行有兩個個數字 $l, r$ ，表示詢問為序列 $A$ 中第 $l$ 個數字到第 $r$ 個數字的總和。

輸出說明：

• 輸出 $q$ 行，每行有一個整數表示該次詢問的答案。
  :::

#include <bits/stdc++.h>

using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<long long> A(n, 0);
    for (int i = 0; i < n; ++i){
        cin >> A[i];
    }
    vector<long long> P(n + 1, 0);
    for (int i = 0; i < n; ++i){
        P[i + 1] = P [i] + A[i];
    }
    int q;
    cin >> q;
    for (int i = 0; i < q; ++i){
        int l, r;
        cin >> l >> r;
        cout << P[r] - P[l-1] << "\n";
    }
    return 0;
}

區間 $[l, r]$ 的部分，我試過題目給的是 1-based index，而非 0-based index，所以在寫的時候可將原本的：

// 0-based index
P[r + 1] - P[l];

改成：

// 1-based index
P[r] - P[l - 1];

或：

// 1-based index
l--, r--;
P[r + 1] - P[l];

然後記得輸出輸入優化，加上用 long long 資料型態，因為測資大到靠北。

2. ZeroJudge e367. 區間Xor：https://zerojudge.tw/ShowProblem?problemid=e367

:::info
內容：
因為c651太恐怖了,出一題簡單版的好了

有一個陣列 A. 且滿足:

1. $A[0] = 0$

2. A[x]=A[x-1]^x $(x \geq 1)$

所以 $A=[0,1,3,0,4,1,7,0,8......]$

而區間 Xor 定義如下：

給定兩個非負整數 $a, b$ $(a \leq b)$

則答案為 A[a]^A[a+1]^A[a+2]^......^A[b-2]^A[b-1]^A[b]

註：^ 為 XOR 的位元運算子。

輸入說明：

• 每行兩個非負整數 $a,b$ $(0 < a \leq b \leq 10^{5})$

輸出說明：

• 輸出 $[a,b]$ 區間的每個數字進行 Xor 運算的結果
  :::

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 100000;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    vector<int> A(MAX_N + 1);
    vector<int> prefixXor(MAX_N + 1);
    
    A[0] = 0;
    prefixXor[0] = A[0];
    
    for (int i = 1; i <= MAX_N; ++i) {
        A[i] = A[i - 1] ^ i;
        prefixXor[i] = prefixXor[i - 1] ^ A[i];
    }

    int a, b;
    while (cin >> a >> b) {
        cout << (prefixXor[b] ^ prefixXor[a - 1]) << '\n';
    }

    return 0;
}

不難，其實就是把 + 號換成 ^ 號而已。

比較難的是 prefixXor[b] ^ prefixXor[a - 1] 這一條該怎麼求出來。

首先我們已經知道 prefix[i] = A[0] ^ A[1] ^ A[2] ^ ... ^ A[i]，表示從 A[0] 到 A[i] 的所有元素的 XOR 結果，則：

$$prefix[b]=A[0]⊕A[1]⊕...⊕A[a−1]⊕A[a]⊕...⊕A[b]$$

$$prefix[a−1]=A[0]⊕A[1]⊕...⊕A[a−1]$$

註：⊕ 為 XOR。

至於在 prefix[b] 的部分，為何會出現 A[a] 呢？不要忘記 [a, b] 區間，到 b 就有 a，只到 a 就不會有 b，如同 prefix[a−1] 那條式子一樣。

另外 XOR 有個很重要的性質（消除律）：

$$x⊕x=0$$

$$0⊕x=x$$

該性質可以消除相同的值：

$$prefix[b]⊕prefix[a−1]=(A[0]⊕⋯⊕A[a−1]⊕A[a]⊕⋯⊕A[b])⊕(A[0]⊕⋯⊕A[a−1])$$

上面兩項中 A[0] ~ A[a-1] 因為出現兩次所以被消掉。

剩下 $A[a]⊕A[a+1]⊕⋯⊕A[b]$ 。

最後得到 $prefix[b]⊕prefix[a−1] = A[a]⊕A[a+1]⊕⋯⊕A[b]$ ，也就是我們要求的區間 Xor。