1310。サブ配列の XOR クエリ
難易度: 中
トピック: 配列、ビット操作、プレフィックス合計
正の整数の配列 arr が与えられます。また、queries[i] = [lefti, righti].
となる配列クエリも与えられます。クエリごとに、要素の XOR を左i から右i まで計算します (つまり、arr[lefti] XOR arr[lefti 1] XOR ... XOR arr[righti] ).
配列の回答を返します。ここで、answer[i] は i 番目の クエリ に対する回答です。
例 1:
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:
制約:
ヒント:
解決策:
プレフィックス XOR テクニックを利用できます。仕組みは次のとおりです:
プレフィックス XOR 配列: プレフィックス XOR 配列を計算します。ここで、prefix[i] は、配列の先頭からインデックス i までのすべての要素の XOR を表します。これにより、任意の部分配列の XOR を定数時間で計算できるようになります。
部分配列の XOR:
これにより、プレフィックス XOR 配列を構築した後、一定時間内に各クエリに答えることができます。
このソリューションを PHP で実装してみましょう: 1310。サブ配列の XOR クエリ
説明:
プレフィックス 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].
クエリへの回答:
- 各クエリ [left, right] について、次を使用して部分配列 arr[left] から arr[right] の XOR を計算します。
- 接頭辞[右] ^ 接頭辞[左 - 1] (左> 0の場合)
- prefix[right] (左 == 0 の場合)
時間計算量:
このアプローチにより、最大 30,000 のサイズの配列に対する最大 30,000 のクエリを効率的に処理できるようになります。
連絡先リンク
このシリーズが役立つと思われた場合は、GitHub で リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!
このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:
以上がサブ配列の XOR クエリの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。