サブ配列の XOR クエリ

1310。サブ配列の XOR クエリ

難易度: 中

トピック: 配列、ビット操作、プレフィックス合計

正の整数の配列 arr が与えられます。また、queries[i] = [left_i, right_i].

となる配列クエリも与えられます。

クエリごとに、要素の XOR を左_i から右_i まで計算します (つまり、arr[left_i] XOR arr[left_i 1] XOR ... XOR arr[right_i] ).

配列の回答を返します。ここで、answer[i] は i ^番目の クエリ に対する回答です。

例 1:

• 入力: arr = [1,3,4,8]、クエリ = [[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]、クエリ = [[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. XOR のプレフィックス合計を計算します。
3. プレフィックス合計値を使用してクエリを処理します。

解決策:

プレフィックス XOR テクニックを利用できます。仕組みは次のとおりです:

アプローチ：

1. プレフィックス XOR 配列: プレフィックス XOR 配列を計算します。ここで、prefix[i] は、配列の先頭からインデックス i までのすべての要素の XOR を表します。これにより、任意の部分配列の XOR を定数時間で計算できるようになります。

2. 部分配列の XOR:

   • 左右のインデックス間の要素の XOR を計算するには:
     • 放置の場合> 0 の場合、prefix[right] ^ prefix[left - 1] として左から右に XOR を計算できます。
     • left == 0 の場合、結果は単に prefix[right] になります。

これにより、プレフィックス XOR 配列を構築した後、一定時間内に各クエリに答えることができます。

プラン：

1. プレフィックス XOR 配列を構築します。
2. クエリごとに、プレフィックス XOR 配列を使用して範囲 [left_i, right_i] の XOR を計算します。

このソリューションを PHP で実装してみましょう: 1310。サブ配列の XOR クエリ

<?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. プレフィックス XOR 構築:

   • 配列プレフィックスは、prefix[i] に arr[0] から arr[i] までのすべての要素の XOR が含まれるように構築されます。
   • たとえば、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] の XOR を計算します。
     • 接頭辞[右] ^ 接頭辞[左 - 1] (左> 0の場合)
     • prefix[right] (左 == 0 の場合)

時間計算量:

• プレフィックス配列の構築: O(n)、n は arr の長さです。
• クエリの処理: O(q)、q はクエリの数です。
• 全体の時間計算量: O(n q)。指定された制約に対して効率的です。

このアプローチにより、最大 30,000 のサイズの配列に対する最大 30,000 のクエリを効率的に処理できるようになります。

連絡先リンク

このシリーズが役立つと思われた場合は、GitHub で リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:

• LinkedIn
• GitHub

以上がサブ配列の XOR クエリの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。