サブ配列の 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 <配列の長さ< li>

ヒント:

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 クエリ

        
説明：
        

         
プレフィックス 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 の場合)
            
          
        
時間計算量:
        

         
プレフィックス配列の構築: O(n)、n は arr の長さです。
         
クエリの処理: O(q)、q はクエリの数です。
         
全体の時間計算量: O(n + q)。これは、指定された制約に対して効率的です。
        
このアプローチにより、最大 30,000 のサイズの配列で最大 30,000 のクエリを効率的に処理できるようになります。
連絡先リンク
このシリーズが役立つと思われた場合は、GitHub でリポジトリにスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!
このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:
        

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