Interroger l'opération OU au niveau du bit d'un tableau donné dans la plage d'index à l'aide de C++

Dans cet article, on nous donne un tableau d'entiers. Notre tâche est de trouver le OU au niveau du bit de tous les nombres dans une plage donnée, par exemple,

Input: arr[] = {1, 3, 1, 2, 3, 4}, q[] = {{0, 1}, {3, 5}}
Output:
3
7
1 OR 3 = 3
2 OR 3 OR 4 = 7
Input: arr[] = {1, 2, 3, 4, 5}, q[] = {{0, 4}, {1, 3}}
Output:
7
7

Dans le problème donné, nous utiliserons une approche par force brute pour le résoudre, puis vérifierons s'il peut être appliqué à des contraintes plus élevées. Sinon, nous optimiserons notre méthode pour s'adapter aux contraintes plus élevées.

Méthode Brute Force

Dans cette méthode, nous parcourons simplement chaque plage et comptons au niveau du bit ou tous les nombres de cette plage et imprimons notre réponse.

Exemple

#include <bits/stdc++.h>
using namespace std;
int main() {
   int arr[] = { 7, 5, 3, 5, 2, 3 };
   int n = sizeof(arr) / sizeof(int); // size of our array
   int queries[][2] = { { 1, 3 }, { 4, 5 } }; // given queries
   int q = sizeof(queries) / sizeof(queries[0]); // number of queries
   for(int i = 0; i < q; i++) { // traversing through all the queries
      long ans = 0;
      for(int j = queries[i][0]; j <= queries[i][1]; j++) // traversing through the range
         ans |= arr[j]; // calculating the answer
      cout << ans << "\n";
   }
   return 0;
}

Output

7
3

La complexité temporelle de cette approche est O(N*Q) où N est la taille du tableau et Q est le nombre de requêtes maintenant, comme vous pouvez le voir, cette complexité ne s'applique pas des contraintes plus élevées, nous allons donc maintenant optimiser notre méthode pour qu'elle fonctionne également pour des contraintes plus élevées.

Méthode efficace

Dans cette méthode, nous compterons le nombre de chiffres de préfixe, puis vérifierons si le nombre a un ensemble spécifique de bits. Si oui, alors nous mettons ce point dans la réponse ; sinon, nous conservons ce point.

Exemple

#include <bits/stdc++.h>

using namespace std;
#define bitt 32
#define MAX (int)10e5

int prefixbits[bitt][MAX];
void bitcount(int *arr, int n) { // making prefix counts
   for (int j = 31; j >= 0; j--) {
      prefixbits[j][0] = ((arr[0] >> j) & 1);
      for (int i = 1; i < n; i++) {
         prefixbits[j][i] = arr[i] & (1LL << j);
         prefixbits[j][i] += prefixbits[j][i - 1];
      }
   }
   return;
}
int check(int l, int r) { // calculating the answer
   long ans = 0; // to avoid overflow we are taking ans as long
   for (int i = 0; i < 32; i++) {
      int x;
      if (l == 0)
         x = prefixbits[i][r];
      else
         x = prefixbits[i][r] - prefixbits[i][l - 1];
      if (x != 0)
         ans = (ans | (1LL << i));
   }
   return ans;
}
int main() {
   int arr[] = {7, 5, 3, 5, 2, 3};
   int n = sizeof(arr) / sizeof(int); // size of our array
   bitcount(arr, n);
   int queries[][2] = {{1, 3}, {4, 5}}; // given queries
   int q = sizeof(queries) / sizeof(queries[0]); // number of queries
   for (int i = 0; i < q; i++) {
      cout << check(queries[i][0], queries[i][1]) << "\n";
   }
   return 0;
}

Sortie

7
3

La complexité temporelle de cette méthode est O(N), où N est la taille du tableau, cette méthode peut donc être adaptée à des contraintes plus élevées.

Explication du code ci-dessus

Dans cette méthode, nous comptons le nombre de chiffres de préfixe et le stockons. Maintenant, nous calculons une requête dans laquelle nous parcourons ce nombre de préfixes et supprimons le nombre de bits de l-1 afin que nous ayons le nombre de bits d'un nombre dans la plage [l, r] puisque nous savons si un bit est défini dans n'importe quel nombre. par conséquent, si vous effectuez un OU au niveau du bit avec un autre nombre, le bit restera défini, donc en utilisant cette propriété de OU au niveau du bit, nous vérifions si le nombre de bits n'est pas nul, ce qui signifie qu'il y a un nombre dans la plage avec le bit défini, nous définissons donc le bit de réponse et continuez la boucle, imprimant enfin la réponse.

Conclusion

Cet article résout le problème du calcul d'une requête OU au niveau du bit dans la plage d'index [L, R] à partir d'un tableau. Nous avons également appris un programme C++ pour résoudre ce problème et une manière complète de résoudre ce problème (normale et efficace). Nous pouvons écrire le même programme dans d'autres langages tels que C, Java, Python et d'autres langages. Nous espérons que cet article vous a été utile.

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!