À l'aide de C++, traduisez ce qui suit en chinois : Requête ET au niveau du bit dans la plage d'index d'un tableau donné

Dans cet article, nous sommes confrontés à un problème dans lequel, étant donné un tableau d'entiers, notre tâche est de trouver le ET au niveau du bit d'une plage donnée, par exemple

Input: arr[ ] = {1, 3, 1, 2, 32, 3, 3, 4, 4}, q[ ] = {{0, 1}, {3, 5}}
Output:
1
0 0
1 AND 31 = 1
23 AND 34 AND 4 = 00
Input: arr[ ] = {1, 2, 3, 4, 510, 10 , 12, 16, 8}, q[ ] = {{0, 42}, {1, 33, 4}}
Output:
0 8
0

Nous allons d'abord appliquer la méthode de force brute et vérifier sa complexité temporelle ; Si notre complexité temporelle n’est pas suffisante, nous essayons de développer une meilleure méthode.

Méthode Brute Force

Dans la méthode donnée, nous allons parcourir la plage donnée, trouver la réponse de notre méthode et l'imprimer.

Exemple

#include <bits/stdc++.h>
using namespace std;
int main() {
   int ARR[] = { 10, 10 , 12, 16, 8 };
   int n = sizeof(ARR) / sizeof(int); // size of our array
   int queries[][2] = { {0, 2}, {3, 4} }; // 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 = 1LL << 32;
      ans -= 1; // making all the bits of ans 1
      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

8
0

Dans cette approche, nous exécutons une boucle sur chaque plage de la requête et imprimons leur ensemble au niveau du bit, de sorte que la complexité globale de notre programme devient O(N*Q ), où N est le taille du tableau et Q est le nombre de requêtes que nous avons actuellement, vous pouvez voir que cette complexité ne se prête pas à des contraintes plus élevées, nous allons donc proposer une méthode plus rapide pour ce problème.

Méthode efficace h2>

Dans ce problème, nous pré-calculons le nombre de bits de préfixe du tableau et calculons le ET au niveau du bit de la plage donnée en vérifiant la contribution des bits définis dans la plage donnée.

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 == r - l + 1)
         ans = ans | 1LL << i;
      }
   return ans;
}
int main() {
   int ARR[] = { 10, 10 , 12, 16, 8 };
   int n = sizeof(ARR) / sizeof(int); // size of our array
   memset(prefixbits, 0, sizeof(prefixbits)); // initializing all the elements with 0
   bitcount(ARR, n);
   int queries[][2] = {{0, 2}, {3, 4}}; // 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

2
0

Dans cette approche, nous utilisons un temps constant pour calculer la requête, réduisant ainsi considérablement la complexité temporelle de O(N*Q) à O(N), où N est maintenant la taille du tableau donné. La procédure peut également être adaptée à des contraintes plus élevées.

Explication du code ci-dessus

Dans cette méthode, nous comptons tous les chiffres du préfixe et les stockons dans l'index. Désormais, lorsque nous calculons la requête, il nous suffit de vérifier si le nombre d'un certain bit est le même que le nombre d'éléments présents dans la plage. Si oui, nous définissons ce bit sur 1 dans x, si non, nous laissons le bit comme si n'importe quel nombre présent dans la plage donnée avait ce bit 0, donc tout le ET au niveau du bit de ce bit sera nul. Voici comment nous procédons calculer le ET au niveau du bit.

Conclusion

Dans cet article, nous avons résolu le problème de l'énumération de toutes les requêtes au niveau du bit ET dans une plage d'index donnée [L, R] sur un grand lot. 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!