Übersetzen Sie mit C++ Folgendes ins Chinesische: Abfrage nach bitweisem AND innerhalb des Indexbereichs eines bestimmten Arrays

In diesem Artikel wird uns ein Problem gestellt, bei dem unsere Aufgabe darin besteht, das bitweise UND eines bestimmten Bereichs zu finden, z. B. 7minus;

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

Wir werden zuerst die Brute-Force-Methode anwenden und die Zeitkomplexität überprüfen. Wenn unsere Zeitkomplexität nicht gut genug ist, versuchen wir, eine bessere Methode zu entwickeln.

Brute-Force-Methode

In der angegebenen Methode durchlaufen wir den angegebenen Bereich, finden unsere Methodenantwort und drucken sie aus.

Beispiel

#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;
}

Ausgabe

8
0

Bei diesem Ansatz führen wir eine Schleife für jeden Bereich der Abfrage aus und drucken ihre Menge bitweise aus, sodass die Gesamtkomplexität unseres Programms O(N*Q) wird, wobei N die ist Da die Größe des Arrays und Q die Anzahl der Abfragen ist, die wir jetzt haben, sehen Sie, dass sich diese Komplexität nicht für höhere Einschränkungen eignet, daher werden wir eine schnellere Methode für dieses Problem finden.

Effiziente Methode

In diesem Problem berechnen wir die Anzahl der Präfixbits des Arrays vorab und berechnen das bitweise UND des angegebenen Bereichs, indem wir den Beitrag der gesetzten Bits im angegebenen Bereich überprüfen.

Beispiel

#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;
}

Ausgabe

2
0

Bei diesem Ansatz verwenden wir eine konstante Zeit, um die Abfrage zu berechnen, wodurch die Zeitkomplexität von O(N*Q) auf O(N), wobei N jetzt ist, erheblich reduziert wird die Größe des angegebenen Arrays. Das Verfahren kann auch an höhere Randbedingungen angepasst werden.

Erklärung des obigen Codes

Bei dieser Methode zählen wir alle Präfixziffern und speichern sie im Index. Wenn wir nun die Abfrage berechnen, müssen wir nur noch prüfen, ob die Anzahl eines bestimmten Bits mit der Anzahl der im Bereich vorhandenen Elemente übereinstimmt. Wenn ja, setzen wir dieses Bit in x auf 1, wenn nein, belassen wir das Bit so, als ob jede im angegebenen Bereich vorhandene Zahl dieses Bit 0 hätte, sodass das gesamte bitweise UND dieses Bits Null ist. So sind wir Berechnen des bitweisen UND.

Fazit

In diesem Artikel haben wir das Problem gelöst, alle Abfragen, die in einem bestimmten Indexbereich [L, R] über einen großen Stapel bitweise UND-verknüpft wurden, aufzuzählen. Wir haben auch ein C++-Programm zur Lösung dieses Problems und einen vollständigen Weg zur Lösung dieses Problems (normal und effizient) gelernt. Wir können das gleiche Programm in anderen Sprachen wie C, Java, Python und anderen schreiben. Wir hoffen, dass dieser Artikel für Sie hilfreich war.

Das obige ist der detaillierte Inhalt vonÜbersetzen Sie mit C++ Folgendes ins Chinesische: Abfrage nach bitweisem AND innerhalb des Indexbereichs eines bestimmten Arrays. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!