Requêtes XOR d'un sous-tableau

1310. Requêtes XOR d'un sous-tableau

Difficulté :Moyen

Sujets : Tableau, manipulation de bits, somme de préfixes

Vous recevez un tableau d'entiers positifs. Vous recevez également les requêtes de tableau où requêtes[i] = [left_i, right_i].

Pour chaque requête, je calcule le XOR des éléments de gauche_i à droite_i (c'est-à-dire arr[left_i] XOR arr[left_i + 1] XOR ... XOR arr[right_i] ).

Renvoyer un tableau de réponse où réponse[i] est la réponse à la i^ième requête.

Exemple 1 :

• Entrée : arr = [1,3,4,8], requêtes = [[0,1],[1,2],[0,3],[3,3]]
• Sortie : [2,7,14,8]
• Explication : La représentation binaire des éléments du tableau est :

  1 = 0001
  3 = 0011
  4 = 0100
  8 = 1000

Les valeurs XOR pour les requêtes sont :

  [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

Exemple 2 :

• Entrée : arr = [4,8,2,10], requêtes = [[2,3],[1,3],[0,0],[0,3]]
• Sortie : [8,0,4,4]

Contraintes :

• 1 <= arr.length, queries.length <= 3 * 10⁴
• 1 <= arr[i] <= 10⁹
• requêtes[i].length == 2
• 0 <= gauche_i <= droite_i < arr.longueur

Indice :

1. Quel est le résultat de x ^ y ^ x ?
2. Calculez la somme des préfixes pour XOR.
3. Traitez les requêtes avec les valeurs de somme des préfixes.

Solution :

On peut utiliser la technique du préfixe XOR. Voici comment cela fonctionne :

Approche:

1. Tableau XOR de préfixe : Nous calculons un tableau XOR de préfixe où le préfixe[i] représente le XOR de tous les éléments depuis le début du tableau jusqu'à l'index i. Cela nous permet de calculer le XOR de n'importe quel sous-tableau en temps constant.

2. XOR d'un sous-tableau :

   • Pour calculer le XOR des éléments entre les indices gauche et droit :
     • Si laissé > 0, nous pouvons calculer le XOR de gauche à droite comme préfixe[droite] ^ préfixe[gauche - 1].
     • Si left == 0, alors le résultat est simplement un préfixe[right].

     Cela nous permet de répondre à chaque requête en temps constant après avoir construit le tableau de préfixes XOR.

     Plan:

     1. Construisez le tableau de préfixes XOR.
     2. Pour chaque requête, utilisez le tableau de préfixe XOR pour calculer le XOR pour la plage [left_i, right_i].

     Implémentons cette solution en PHP : 1310. Requêtes XOR d'un sous-tableau
     

     <?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]
     ?>
     

     Explication:

     1. Préfixe XOR Construction :

        • Le préfixe du tableau est construit de telle sorte que le préfixe[i] contient le XOR de tous les éléments de arr[0] à arr[i].
        • Par exemple, étant donné arr = [1, 3, 4, 8], le tableau de préfixes sera [1, 1^3, 1^3^4, 1^3^4^8] ou [1, 2 , 6, 14].

     2. Répondre aux requêtes :

        • Pour chaque requête [gauche, droite], nous calculons le XOR du sous-tableau arr[left] à arr[right] en utilisant :
          • préfixe[droite] ^ préfixe[gauche - 1] (si gauche > 0)
          • préfixe[droite] (si gauche == 0)

     Complexité temporelle :

     • Construction du tableau de préfixes : O(n), où n est la longueur de l'arr.
     • Traitement des requêtes : O(q), où q est le nombre de requêtes.
     • Complexité temporelle globale : O(n + q), qui est efficace pour les contraintes données.

     Cette approche garantit que nous pouvons traiter efficacement jusqu'à 30 000 requêtes sur un tableau d'une taille allant jusqu'à 30 000.

     Liens de contact

     Si vous avez trouvé cette série utile, pensez à donner une étoile au référentiel sur GitHub ou à partager la publication sur vos réseaux sociaux préférés ?. Votre soutien signifierait beaucoup pour moi !

     Si vous souhaitez du contenu plus utile comme celui-ci, n'hésitez pas à me suivre :

     • LinkedIn
     • GitHub

     Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!