Berechnen Sie mithilfe eines Baumarrays (Offline-Abfrage) die Anzahl der Elemente größer als K im Bereich L bis R

Im Bereich der Informatik müssen wir mit großen Datensätzen umgehen, zu denen Abfrageauswahl- und Aktualisierungsvorgänge gehören. Die Durchführung dieser Vorgänge in Echtzeit mit geringer zeitlicher Komplexität ist für Entwickler eine anspruchsvolle Aufgabe.

Die Verwendung von Fenwick-Bäumen ist eine effektive Möglichkeit, diese bereichsbasierten Abfrageprobleme zu lösen.

Fenwick Tree ist eine Datenstruktur, die Elemente effizient aktualisieren und die Präfixsumme von Zahlen in einer Tabelle berechnen kann. Er wird auch als binärer Indexbaum bezeichnet.

In diesem Artikel besprechen wir, wie man mithilfe des Fenwick-Baums die Anzahl der Elemente größer als K im Bereich L bis R ermittelt.

Eingabe- und Ausgabeszenarien

Angenommen, Sie haben ein Array mit N Elementen und möchten die Anzahl der Elemente im Array ermitteln, die größer als K im Bereich L bis R sind.

Input: 
arr = {1, 15, 12, 13, 6, 18, 14, 10, 23, 41, 16, 9}
N = 11, K = 17, L = 1, R = 8
Output: 
2

Was ist eine Offline-Abfrage?

Offline-Abfrage ist eine Abfrageoperation, die an einem vorgegebenen Datensatz durchgeführt wird. Mit anderen Worten: Diese Vorgänge werden nur für die Datensätze ausgeführt, die während der Verarbeitung der Abfrage nicht weiter geändert werden.

Mit Fenwick Tree

Hier verwenden wir einen Fenwick-Baum, der an jedem Knoten Vektoren hat, die alle Elemente des Arrays der Reihe nach enthalten. Anschließend verwenden wir die binäre Suche, um jede Abfrage zu beantworten und die Anzahl der Elemente zu zählen.

• Erstellen Sie zwei Funktionen, updateTree() und total(), zum Aktualisieren bzw. Abrufen der Präfixsumme in BIT.

• Als nächstes erstellen Sie eine weitere Funktion, die Elemente im Bereich L bis R zählt, die größer als „K“ sind. Diese Funktion akzeptiert die Eingabewerte „arr“, „N“, „L“, „R“ und „K“.

• Die Zählung wird berechnet, indem die kumulative Summe von K von der kumulativen Summe der maximalen Reichweite N subtrahiert wird.

Um Elemente außerhalb des Bereichs auszuschließen, subtrahieren Sie die kumulative Summe von L-1 (wenn L größer als 1 ist).

Beispiel

#include <iostream>
#include <vector>
using namespace std;

// Updating the Fenwick Tree
void updateTree(vector<int>& BIT, int index, int value) {
   while (index < BIT.size()) {
      BIT[index] += value;
      index += index & -index;
   }
}

int total(vector<int>& BIT, int index) {
   int result = 0;
   while (index > 0) {
      result += BIT[index];
      index -= index & -index;
   }
   return result;
}

// Counting the number of elements
int elementsGreaterThanK(vector<int>& arr, int N, int K, int L, int R) {
   vector<int> BIT(N+1, 0);

   for (int i = L; i <= R; i++) {
      updateTree(BIT, arr[i], 1);
   }

   int count = total(BIT, N) - total(BIT, K);
   if (L > 1) {
      count -= total(BIT, L-1);
   }
   return count;
}

int main() {
   vector<int> arr = {0, 5, 2, 3, 6, 8, 7, 1, 8, 4, 6, 9};
   int N = 11; // Total range of values
   int K = 4; // Highest value
   int L = 1; // Start index of the range
   int R = 8; // End index of the range

   int count = elementsGreaterThanK(arr, N, K, L, R);
   cout << "Number of elements greater than " << K << " in the range [" << L << ", " << R << "]: " << count << endl;

   return 0;
}

Ausgabe

Number of elements greater than 4 in the range [1, 8]: 5

Alternative Methode

Hier erstellen wir einen separaten Vektor zum Speichern der Abfrage. Jede Abfrage besteht aus zwei Variablen, index und val. index wird verwendet, um die Position im Array zu speichern, während val verwendet wird, um den Wert des Elements an diesem Index zu speichern. Dieser Ansatz ermöglicht es Entwicklern, eine Vielzahl von Abfragevorgängen durchzuführen. Darüber hinaus verwenden wir BIT, um für jede Abfrage die Anzahl der Elemente zu zählen, die größer als K sind.

Beispiel

#include <iostream>
#include <vector>
using namespace std;
struct Query {
   int index;
   int val;
};

void updateTree(vector<int>& BIT, int index, int value) {
   while (index < BIT.size()) {
      BIT[index] += value;
      index += index & -index;
   }
}

int total(vector<int>& BIT, int index) {
   int result = 0;
   while (index > 0) {
      result += BIT[index];
      index -= index & -index;
   }
   return result;
}

vector<int> elementsGreaterThanK(vector<int>& arr, vector<Query>& queries, int K) {
   int N = arr.size();
   vector<int> BIT(N+1, 0);
   vector<int> result;

   for (int i = 0; i < N; i++) {
      updateTree(BIT, i+1, (arr[i] > K) ? 1 : 0);
   }

   for (auto query : queries) {
      if (query.val > K) {
         result.push_back(total(BIT, query.index));
      }
      else {
         result.push_back(0);
      }
   }

   return result;
}

int main() {
   vector<int> arr = {3, 14, 32, 7, 11, 5, 8, 6, 16, 2, 15};
   vector<Query> queries = {{2, 4}, {5, 3}, {3, 6}, {0, 3}};
   int K = 2;

   vector<int> counts = elementsGreaterThanK(arr, queries, K);

   for (int count : counts) {
      cout << "Number of elements greater than " << K << ": " << count << endl;
   }

   return 0;
}

Ausgabe

Number of elements greater than 2: 2
Number of elements greater than 2: 5
Number of elements greater than 2: 3
Number of elements greater than 2: 0

Fazit

Wir können das Array einfach von Index L bis R iterieren und jedes Mal 1 hinzufügen, wenn das Array-Element größer als K ist, um die Antwort auf jede Abfrage zu finden. Um jedoch die zeitliche Komplexität zu reduzieren, verwenden wir den Fenwick-Baum, um solche Abfrageoperationen durchzuführen. Wir können anstelle des Fenwick-Baums auch Line Segment Tree und Sparse Table verwenden, um solche Abfrageoperationen durchzuführen.

Das obige ist der detaillierte Inhalt vonBerechnen Sie mithilfe eines Baumarrays (Offline-Abfrage) die Anzahl der Elemente größer als K im Bereich L bis R. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!