1. 概要

このチュートリアルでは、特定の範囲内のすべての数値のXORを見つける問題を示します。

まず、素朴なアプローチについて説明します。 次に、より良い解決策を得るためにそれをどのように改善できるかを見ていきます。 最後に、両方のアプローチの比較を示します。

2. 問題の定義

この問題では、サイズの配列と複数のクエリが与えられます。 各クエリで、範囲内のすべての要素間のビット単位のXOR演算を計算するように求められます。

配列はクエリ間で変更されません。 つまり、配列内の特定の要素の値を変更するように要求するクエリはありません。

したがって、配列内のクエリごとに、の値を返す必要があります。ここで、は範囲内の要素間のビット単位のXOR演算です。

3. XORの背景

ご存知のように、ビット単位のXOR演算は、2つの数値を少しずつ処理します。 各ビットについて、結果は提示された表から抽出できます。

ご覧のとおり、両方のビットが類似している場合、XORはゼロに等しくなります。 それ以外の場合、結果は1になります。 言い換えると、ビット単位のXOR演算は、1の数が偶数の場合はゼロに等しく、1の数が奇数の場合は1に等しくなります。

また、注意すべき重要な点は、ビット単位のXORが各ビットで独立して機能することです。 つまり、各ビットの結果は、数値内の他のビットの結果には影響しません。 セクション5で解決策について説明するときは、これらの注意事項に留意してください。

4. 素朴なアプローチ

まず、素朴なアプローチを探ります。 そのアルゴリズムを見てみましょう：

最初に、アルゴリズムは答えをゼロに設定します。 その後、範囲の要素を反復処理し、そのすべての要素のXORを計算します。 最後に、計算された答えを返します。

単純なアプローチの複雑さはです。ここで、は配列のサイズです。 この複雑さの背後にある理由は、最悪の場合、すべての要素を反復処理することになる可能性があるためです。

したがって、各クエリの複雑さは線形です。

5. プレフィックス-XORアプローチ

素朴なアプローチを改善してみましょう。

5.1. 事前計算のアイデア

各ビットは個別に計算されるため、各ビットの問題を個別に解決できます。 その後、完全なソリューションを作成できます。

問題が個々のビットを処理することであったと仮定します。 前と同じように、範囲内のこのビットのXORを計算する必要があります。 まず、という名前のブール配列を作成しましょう。 各セルには、範囲内のすべてのビットのプレフィックスXORを格納します。

セクション3のXOR演算の定義から、i th プレフィックスのビット数が偶数の場合、i thセルはゼロに等しくなることがわかります。 それ以外の場合、i thセルは1に等しくなります。

それでは、元の問題を確認しましょう。 範囲内のビットのXORを見つける必要があります。つまり、範囲内の1の数が偶数か奇数かを確認する必要があります。

これを行うために、2つの値を考えてみましょう。 最初の値は、の範囲をカバーするです。 この範囲は、必要な範囲のすべての要素に加えて、範囲内にあるいくつかの追加要素をカバーします。 したがって、2番目の値はであり、範囲をカバーします。

これらの2つの値から、範囲の値を結論付けることができます。

5.2. ソリューションのアイデア

配列を計算した後、各クエリで考慮すべき4つのケースがあります。

  1. 両方ともゼロに等しい。 ゼロに等しいので、1の数は範囲を開始する前でもあります。 また、範囲を処理した後も1の数は残ります。 これは、範囲内の1の数も同じである場合にのみ発生する可能性があります。
  2. 両方とも等しい。 1に等しいので、範囲に入る前の1の数は奇数です。 また、1に等しいので、この範囲の1の数も奇数です。 これは、範囲内の1の数が偶数の場合にのみ保持できます。これにより、ビットのパリティは同じままになります。
  3. は1に等しく、ゼロに等しくなります。 範囲内の1の数は奇数ですが、範囲内で偶数になるように変化するため、範囲内の1の数は奇数であると結論付けることができます。
  4. はゼロに等しく、1に等しい。 範囲内の1の数は偶数ですが、範囲内で奇数に変化するため、範囲内の1の数は奇数であると結論付けることができます。

両方が同じ値である場合、答えはゼロであることがわかります。 それ以外の場合、答えは1になります。

これは、との間でXOR演算を実行するのと同じです。 したがって、の答えは単純にです。ここで、はビット単位のXOR演算です。

5.3. 事前計算アルゴリズム

一般的な解を形成するには、プレフィックスXOR配列を計算する必要があります。

このステップの実装を見てみましょう。

このアイデアは、動的計画法に基づいています。 最初は、の答えがゼロに等しいことを知っています。

次に、各範囲について、範囲からその答えを計算できます。 これら2つの範囲の唯一の違いはです。 したがって、範囲に追加する必要があります。 言い換えると、 。 最後に、計算された配列を返します。

事前計算ステップの複雑さはです。ここで、は配列内の要素の数です。

5.4. 質問に答える

配列を作成した後、セクション5.2で説明したのと同じアプローチで各クエリに答えることができます。

クエリに答えるアルゴリズムを見てみましょう。

ご覧のとおり、セクション5.2で説明したように、との間のXORを返すだけです。 各クエリへの回答の複雑さはです。

6. 比較

両方のアプローチの比較を示す表を検討してください。

明らかに、複雑さの比較に関しては、プレフィックスXORアプローチの方が優れています。 ただし、事前に配列を計算する必要があります。 その後、の複雑さで各クエリに効率的に答えることができます。

覚えておくべきことの1つは、これは配列の要素の値を変更しない場合にのみ当てはまるということです。 単一の要素の値を変更するか、範囲内の要素のXORのクエリに応答するかの、2種類のクエリがある場合、どちらのアプローチも同じ複雑さを持ちます。

したがって、より単純な単純なアプローチを使用できます。

7. 結論

このチュートリアルでは、特定の範囲の数値のXORを計算する問題について説明しました。 まず、素朴なアプローチを紹介しました。 次に、プレフィックスXORアプローチの理論的アイデアと実装について説明しました。

最後に、2つのアプローチの概要を比較しました。