# 1310. 子數組異或查詢 # 題目地址（1310. 子數組異或查詢） <https://leetcode-cn.com/problems/xor-queries-of-a-subarray/> ## 題目描述 ``` <pre class="calibre18">``` 有一個正整數數組 arr，現給你一個對應的查詢數組 queries，其中 queries[i] = [Li, Ri]。 對于每個查詢 i，請你計算從 Li 到 Ri 的 XOR 值（即 arr[Li] xor arr[Li+1] xor ... xor arr[Ri]）作為本次查詢的結果。 并返回一個包含給定查詢 queries 所有結果的數組。 示例 1： 輸入：arr = [1,3,4,8], queries = [[0,1],[1,2],[0,3],[3,3]] 輸出：[2,7,14,8] 解釋： 數組中元素的二進制表示形式是： 1 = 0001 3 = 0011 4 = 0100 8 = 1000 查詢的 XOR 值為： [0,1] = 1 xor 3 = 2 [1,2] = 3 xor 4 = 7 [0,3] = 1 xor 3 xor 4 xor 8 = 14 [3,3] = 8 示例 2： 輸入：arr = [4,8,2,10], queries = [[2,3],[1,3],[0,0],[0,3]] 輸出：[8,0,4,4] 提示： 1 <= arr.length <= 3 * 10^4 1 <= arr[i] <= 10^9 1 <= queries.length <= 3 * 10^4 queries[i].length == 2 0 <= queries[i][0] <= queries[i][1] < arr.length ``` ``` ## 前置知識 - 前綴和 ## 暴力法 ### 思路 最直觀的思路是雙層循環即可，果不其然超時了。 ### 代碼 ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">xorQueries</span><span class="hljs-params">(self, arr: List[int], queries: List[List[int]])</span> -> List[int]:</span> res = [] <span class="hljs-keyword">for</span> (L, R) <span class="hljs-keyword">in</span> queries: i = L xor = <span class="hljs-params">0</span> <span class="hljs-keyword">while</span> i <= R: xor ^= arr[i] i += <span class="hljs-params">1</span> res.append(xor) <span class="hljs-keyword">return</span> res ``` ``` ## 前綴表達式 ## 公司 - 暫無 ### 思路 比較常見的是前綴和，這個概念其實很容易理解，即一個數組中，第 n 位存儲的是數組前 n 個數字的和。 對 \[1,2,3,4,5,6\] 來說，其前綴和可以是 pre=\[1,3,6,10,15,21\]。我們可以使用公式 pre\[??\]=pre\[???1\]+nums\[??\]得到每一位前綴和的值，從而通過前綴和進行相應的計算和解題。其實前綴和的概念很簡單，但困難的是如何在題目中使用前綴和以及如何使用前綴和的關系來進行解題。 這道題是前綴對前綴異或，我們利用了異或的性質 `x ^ y ^ x = y`。  ### 代碼 代碼支持 Python3，Java，C++： Python Code： ``` <pre class="calibre18">``` <span class="hljs-title">#</span> <span class="hljs-title"># @lc app=leetcode.cn id=1218 lang=python3</span> <span class="hljs-title">#</span> <span class="hljs-title"># [1218] 最長定差子序列</span> <span class="hljs-title">#</span> <span class="hljs-title"># @lc code=start</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">xorQueries</span><span class="hljs-params">(self, arr: List[int], queries: List[List[int]])</span> -> List[int]:</span> pre = [<span class="hljs-params">0</span>] res = [] <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(len(arr)): pre.append(pre[i] ^ arr[i]) <span class="hljs-keyword">for</span> (L, R) <span class="hljs-keyword">in</span> queries: res.append(pre[L] ^ pre[R + <span class="hljs-params">1</span>]) <span class="hljs-keyword">return</span> res <span class="hljs-title"># @lc code=end</span> ``` ``` Java Code： ``` <pre class="calibre18">``` <span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span>[] xorQueries(<span class="hljs-keyword">int</span>[] arr, <span class="hljs-keyword">int</span>[][] queries) { <span class="hljs-keyword">int</span>[] preXor = <span class="hljs-keyword">new</span> <span class="hljs-keyword">int</span>[arr.length]; preXor[<span class="hljs-params">0</span>] = <span class="hljs-params">0</span>; <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-params">1</span>; i < arr.length; i++) preXor[i] = preXor[i - <span class="hljs-params">1</span>] ^ arr[i - <span class="hljs-params">1</span>]; <span class="hljs-keyword">int</span>[] res = <span class="hljs-keyword">new</span> <span class="hljs-keyword">int</span>[queries.length]; <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-params">0</span>; i < queries.length; i++) { <span class="hljs-keyword">int</span> left = queries[i][<span class="hljs-params">0</span>], right = queries[i][<span class="hljs-params">1</span>]; res[i] = arr[right] ^ preXor[right] ^ preXor[left]; } <span class="hljs-keyword">return</span> res; } ``` ``` C++ Code: ``` <pre class="calibre18">``` <span class="hljs-keyword">class</span> Solution { <span class="hljs-keyword">public</span>: <span class="hljs-params">vector</span><<span class="hljs-keyword">int</span>> xorQueries(<span class="hljs-params">vector</span><<span class="hljs-keyword">int</span>>& arr, <span class="hljs-params">vector</span><<span class="hljs-params">vector</span><<span class="hljs-keyword">int</span>>>& queries) { <span class="hljs-params">vector</span><<span class="hljs-keyword">int</span>>res; <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-params">1</span>; i<arr.size(); ++i){ arr[i]^=arr[i<span class="hljs-params">-1</span>]; } <span class="hljs-keyword">for</span>(<span class="hljs-params">vector</span><<span class="hljs-keyword">int</span>>temp :queries){ <span class="hljs-keyword">if</span>(temp[<span class="hljs-params">0</span>]==<span class="hljs-params">0</span>){ res.push_back(arr[temp[<span class="hljs-params">1</span>]]); } <span class="hljs-keyword">else</span>{ res.push_back(arr[temp[<span class="hljs-params">0</span>]<span class="hljs-params">-1</span>]^arr[temp[<span class="hljs-params">1</span>]]); } } <span class="hljs-keyword">return</span> res; } }; ``` ``` **復雜度分析** 其中 N 為數組 arr 長度， M 為 queries 的長度。 - 時間復雜度：O(N?M)O(N \* M)O(N?M) - 空間復雜度：O(N)O(N)O(N) ## 關鍵點解析 - 異或的性質 x ^ y ^ x = y - 前綴表達式 ## 相關題目 - [303. 區域和檢索 - 數組不可變](https://leetcode-cn.com/problems/range-sum-query-immutable/description/)  - [1186.刪除一次得到子數組最大和](https://lucifer.ren/blog/2019/12/11/leetcode-1186/) 大家對此有何看法，歡迎給我留言，我有時間都會一一查看回答。更多算法套路可以訪問我的 LeetCode 題解倉庫：<https://github.com/azl397985856/leetcode> 。 目前已經 37K star 啦。 大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。