子數組的異或查詢

1310。子數組的異或查詢

難度：中

主題：陣列、位元操作、前綴和

給你一個正整數數組 arr 。您還會獲得數組查詢，其中 requests[i] = [left_i, right_i].

對於每個查詢，我計算從左_i到右_i元素的異或（即arr[left_i] XOR arr[left_i 1] 異或... 異或arr[右_i] ).

回傳陣列答案，其中answer[i]是第i^第查詢的答案。

範例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 4
• 1 9
• 查詢[i].length == 2
• 0 i i

提示：

1. x ^ y ^ x 的結果是什麼？
2. 計算異或的前綴和。
3. 使用前綴總和值處理查詢。

解：

我們可以利用前綴XOR技術。其工作原理如下：

方法：

1. 前綴異或數組：我們計算一個前綴異或數組，其中 prefix[i] 表示從數組開頭到索引 i 的所有元素的異或。這使我們能夠在恆定時間內計算任何子數組的異或。

2. 子數組的異或:

   • 計算左索引與右索引之間元素的異或：
     • 如果離開> 0，我們可以從左到右計算 XOR 作為 prefix[right] ^ prefix[left - 1]。
     • 如果 left == 0，那麼結果就是 prefix[right]。

這使我們能夠在構造前綴 XOR 數組後在恆定時間內回答每個查詢。

計劃：

1. 建立前綴異或陣列。
2. 對於每個查詢，使用前綴 XOR 陣列來計算範圍 [left_i, right_i] 的 XOR。

讓我們用 PHP 實作這個解：1310。子數組的異或查詢

<?php
/**
 * @param Integer[] $arr
 * @param Integer[][] $queries
 * @return Integer[]
 */
function xorQueries($arr, $queries) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example 1
$arr1 = [1, 3, 4, 8];
$queries1 = [[0, 1], [1, 2], [0, 3], [3, 3]];
print_r(xorQueries($arr1, $queries1)); // Output: [2, 7, 14, 8]

// Example 2
$arr2 = [4, 8, 2, 10];
$queries2 = [[2, 3], [1, 3], [0, 0], [0, 3]];
print_r(xorQueries($arr2, $queries2)); // Output: [8, 0, 4, 4]
?>

解釋：

1. 前綴異或構造:

   • 建立數組前綴，使得 prefix[i] 包含從 arr[0] 到 arr[i] 的所有元素的異或。
   • 例如，給定arr = [1, 3, 4, 8]，前綴數組將為[1, 1^3, 1^3^4, 1^3^4^8] 或[1, 2 , 6, 14].

2. 回答查詢:

   • 對於每個查詢 [left, right]，我們使用以下方法計算子數組 arr[left] 到 arr[right] 的異或：
     • 字首[右] ^ 字首[左 - 1]（若左 > 0）
     • 字首[右]（如果左== 0）

時間複雜度：

• 建構前綴數組：O(n)，其中n是arr的長度。
• 處理查詢：O(q)，其中q是查詢數量。
• 總體時間複雜度：O(n q)，對於給定的限制是有效的。

這種方法確保我們可以有效地處理大小高達 30,000 的陣列上的多達 30,000 個查詢。

聯絡連結

如果您發現本系列有幫助，請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！

如果您想要更多類似的有用內容，請隨時關注我：

• 領英
• GitHub

以上是子數組的異或查詢的詳細內容。更多資訊請關注PHP中文網其他相關文章！