題目

1310. XOR Queries of a Subarray
難度: 中等偏易

題意

給定一整數陣列arr；給定一整數陣列的陣列queries，其中queries[i]為[left, right]陣列，代表一個區間[left, right]。
回傳大小與queries相同之整數陣列answer，其中answer[i]代表arr在區間queries[i]所有元素異或(exclusive or)的值。

方向

先複習異或(exclusive or)的真值表

異或有個重要的性質: 對合(involution)，也就是其逆函數等同於自身。
A XOR B XOR B = A XOR 0 = A
白話點就是，自己異或自己，就會把自己消除。

這題最naive的作法，就是區間每個元素一個個來異或，時間複雜度為O(N^2)。

而異或有著對合的性質，我們可以利用此特性，將這題轉化為類似前綴和(prefix)的題目。
先建立一個前綴異或陣列prefix_xor，prefix_xor[i]代表arr從索引零到i的異或值。
對於題目每個要求的區間[left, right]，只需用prefix_xor[right] XOR prefix_xor[left - 1]即可求得。
XOR prefix_xor[left - 1]的作用就是把索引零到left之前的異或值都消除掉。

實作

class Solution
{
public:
    vector<int> xorQueries(vector<int>& arr, const vector<vector<int>>& queries)
    {
        size_t arr_size = arr.size();
        for (size_t i = 1; i < arr_size; i++)
            arr[i] ^= arr[i - 1];

        size_t n = queries.size();
        vector<int> res(n, 0);
        for (size_t i = 0; i < n; i++)
            res[i] = arr[queries[i][1]]
                     ^ (queries[i][0] == 0 ? 0 : arr[queries[i][0] - 1]);
        return res;
    }
};

分析

若arr長度為N，quireis長度為M
時間複雜度: O(N + M) = O(max(M, N))，建立前綴異或O(N)，建立answerO(M * 1)。
空間複雜度: O(1)，這題直接把前綴存回arr中，因此無須額外空間。

結果