Fragen Sie die Untergrenze von K mithilfe des Präfixes und der Array-Aktualisierung des Baumarrays ab

Ein primäres Sequenzsummenarray ist eine Sammlung, die die Summe verschachtelter Elemente akkumuliert, bis ein bestimmter Index erreicht ist. Dies ist eine Strategie, die beim kombinatorischen Refactoring weit verbreitet ist, um die Zeitkomplexität zu optimieren. Baumarrays, auch bekannt als Binary Index Trees (BITs), sind eine Datenbankform, die Elemente effizient aktualisiert und die Summe vorheriger Sequenzen in logarithmischer Zeitkomplexität berechnet.

In diesem Artikel besprechen wir, wie man Fenwick Tree in C++ mit modernen Verbesserungen verwendet, um die kleinere Grenzwertgrenze für einen bestimmten Wert, genannt K, aus einer Reihe summierter Arrays aufzudecken.

Grammatik

Die Syntax definiert zwei Funktionen, Aktualisierung und Abfrage, sowie eine Hauptfunktion für einen Fenwick-Baum, eine Datenstruktur für effiziente Bereichsabfrage- und Aktualisierungsvorgänge. Die Aktualisierungsfunktion akzeptiert eine Index-IDX, einen Wertwert, die Größe des Arrays n und das Fenwick-Baum-Array-BIT. Es aktualisiert den Fenwick-Baum, indem es val zum Knoten am Index-IDX und allen seinen Vorfahren hinzufügt. Die Abfragefunktion akzeptiert eine Index-IDX und ein Fenwick-Baum-Array-BIT. Es gibt die kumulative Summe vom Wurzelknoten zum Knoten mit der Index-IDX zurück. Die Hauptfunktion deklariert die Größe n des Arrays, das Präfix und das Array arr, und das Fenwick-Baum-Array BIT wird auf 0 initialisiert.

void update(int idx, int val, int n, int BIT[]) {
   while (idx <= n) {
      BIT[idx] += val;
      idx += (idx & -idx);
   }
}
int query(int idx, int BIT[]) {
   int sum = 0;
   while (idx > 0) {
      sum += BIT[idx];
      idx -= (idx & -idx);
   }
   return sum;
}
// Driver code
int main() {
   int n; 
   int arr[n+1];
   int BIT[n+1] = {0}; 
   return 0;
}

Algorithmus

Um den Mindestwert von K im Präfix und Array mit der Aktualisierung des Fenwick-Baums zu bestimmen, führen Sie die folgenden komplexen Schritte aus -

• Instanziieren Sie einen Fenwick-Baum (BIT) der Größe n+1 und initialisieren Sie alle Elemente auf 0.

• Verwenden Sie die Funktion update(), um den Fenwick-Baum mit dem angegebenen Präfix und Array zu ändern.

• Führen Sie eine Abfrage für den Fenwick-Baum aus, um die Untergrenze von K zu bestimmen. Iterieren Sie vom höchstwertigen Bit in der binären Darstellung von n bis zum niedrigstwertigen Bit. Verwenden Sie die Funktion query(), um zu überprüfen, ob die aktuelle Präfixsumme kleiner oder gleich K ist. Wenn diese Bedingung erfüllt ist, wird die aktuelle Präfixsumme von K subtrahiert und der Index aktualisiert, um zum nächsten Bit zu gelangen. Wenn die Bedingung nicht erfüllt ist, fahren Sie mit dem nächsten Bit fort, ohne den Index zu aktualisieren.

• Nachdem alle Bits durchlaufen wurden, stellt der Index das Präfix und die untere Grenze von K im Array dar.

• Geben Sie den erhaltenen Index als Untergrenze von K aus.

Methode

• Methode 1 – Führen Sie eine binäre Suche im Fenwick-Baum durch. Bei dieser Methode führen wir eine binäre Suche im Fenwick-Baum durch, um die Untergrenze von K zu finden.

• Methode 2 – Binäre Suche mit verzögerter Ausbreitung auf dem Fenwick-Baum.

Methode 1

Um dieses Problem zu lösen, setzen wir zunächst den linken und rechten Zeiger auf 1 bzw. n (was die Größe des Präfixes und des Arrays angibt) und verwenden dann eine binäre Suchstrategie, um den Index i zu bestimmen, der der größten Präfixsumme kleiner als entspricht oder gleich K. Abhängig davon, ob der Wert der Präfixsumme [i] kleiner oder gleich K ist, wird dann die Position des linken Zeigers oder des rechten Zeigers aktualisiert.

Beispiel

Der grundlegende Mechanismus dieses Codes besteht darin, eine Datenstruktur namens Fenwick Tree (auch bekannt als Binary Indexed Tree) zu verwenden. Sein Zweck besteht darin, die untere Grenze des angegebenen Werts „k“ im Präfix-Summen-Array zu bestimmen. Dies wird erreicht, indem ein Fenwick-Baum mithilfe einer Aktualisierungsfunktion erstellt wird, die das Präfix und den Wert jedes Elements im Array an der entsprechenden Position im Fenwick-Baum zusammenführt.

Die Funktion

findLowerBound verwendet dann einen binären Suchalgorithmus, um durch Abfragen der Funktion die untere Grenze von „k“ im Präfix und Array herauszufinden. Diese Funktion berechnet die kumulative Summe der Werte bis zum aktuellen Index im Fenwick-Baum. Schließlich identifiziert der Code das Präfix und den Index der unteren Grenze von „k“ im Array und zeigt das Ergebnis auf der Konsole an.

#include <iostream>
using namespace std;
void update(int i, int v, int n, int b[]) {
    while (i <= n) {
        b[i] += v;
        i += (i & -i);
    }
}
int query(int i, int b[]) {
    int s = 0;
    while (i > 0) {
        s += b[i];
        i -= (i & -i);
    }
    return s;
}
int findLowerBound(int k, int n, int p[], int b[]) {
    int l = 1, r = n, idx = 0;
    while (l <= r) {
        int m = (l + r) / 2;
        int msum = query(m, b);
        if (msum <= k) {
            idx = m;
            l = m + 1;
        } else {
            r = m - 1;
        }
    }
    return idx;
}
int main() {
    int n = 5;
    int p[] = {0, 1, 3, 6, 10, 15};
    int b[n + 1] = {0};
    for (int i = 1; i <= n; i++) {
        update(i, p[i], n, b);
    }
    int k = 10, idx;
    idx = findLowerBound(k, n, p, b);
    cout << "The lower bound of " << k << " is at index " << idx << " in the prefix sum array." << endl;
    return 0;
}

Ausgabe

The lower bound of 10 is at index 3 in the prefix sum array.

Methode 2

Um Fenwick-Bäume weiter zu optimieren, kann eine Technik namens Lazy Propagation verwendet werden. Bei diesem Ansatz werden Aktualisierungen des Fenwick-Baums verschoben, bis sie tatsächlich benötigt werden, wodurch die Anzahl der Aktualisierungen reduziert und der Abfrageprozess effizienter gestaltet wird.

Beispiel

Der Code bietet eine Lösung zum Auffinden der Untergrenze eines bestimmten Werts K in einem Präfix-Summen-Array. Ein Präfixsummen-Array ist ein Array, bei dem jedes Element die Summe der Elemente von Index 0 bis zu diesem Index im ursprünglichen Array ist. Die untere Grenze ist der erste Index im Präfixsummen-Array, sodass die Summe der Elemente bis zu diesem Index gleich oder größer als K ist. Die Lösung nutzt die Fenwick-Baumdatenstruktur und die Verzögerungsausbreitungstechnik, um die Effizienz der Lösung zu verbessern. Der Code enthält Funktionen zum Ändern von Fenwick-Bäumen, zum Berechnen von Präfixsummen und zum Finden von Untergrenzen. Der Code initialisiert außerdem Präfixsummen-Arrays, Fenwick-Bäume und Arrays mit verzögerter Ausbreitung. Schließlich werden das Präfix und die untere Grenze von K im Array ausgegeben.

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

void update(int idx, int val, int n, int ft[], int lz[]) {
   while (idx  <= n) ft[idx] += val, idx += (idx & -idx);
}

int getPrefixSum(int idx, int ft[]) {
   int sum = 0;
   while (idx > 0) sum += ft[idx], idx -= (idx & -idx);
   return sum;
}

int findLowerBound(int K, int n, int ps[], int ft[], int lz[]) {
   int l = 1, r = n, lb = 0;
   while (l  <= r) {
      int m = (l + r) / 2, s = getPrefixSum(m, ft) + lz[m];
      if (s  <= K) lb = m, l = m + 1;
      else r = m - 1;
   }
   return lb;
}

int main() {
   int n = 5;
   int ps[] = {0, 1, 3, 6, 10, 15};
   int ft[n + 1], lz[n + 1]; memset(ft, 0, sizeof(ft)); memset(lz, 0, sizeof(lz));
   for (int i = 1; i  <= n; i++) update(i, ps[i] - ps[i - 1], n, ft, lz);
   int K = 10;
   int lb = findLowerBound(K, n, ps, ft, lz);
   cout << "For the given array with size " << n << " and prefix sum array [";
   for (int i = 1; i <= n; i++) {
      cout << ps[i];
      if (i < n) cout << ", ";
   }
   cout << "], the lower bound of " << K << " is at index " << lb << " in the prefix sum array." << endl;
   return 0;
}

Ausgabe

For the given array with size 5 and prefix sum array [1, 3, 6, 10, 15], the lower bound of 10 is at index 4 in the prefix sum array.

Fazit

Diskussion über das Mining schwer fassbarer K-Wert-Schwellenwerte aus gut gestalteten Präfixen und Arrays, erweitert durch ein Update, das den cleveren Fenwick-Baum-Algorithmus aus der Welt der C++-Programmierung nutzt. Tauchen Sie ein in die Komplexität zweier effizienter Methoden: binäre Suche auf Fenwick-Bäumen und binäre Suche auf Fenwick-Bäumen mit verzögerter Ausbreitung. Wählen Sie sorgfältig die am besten geeignete Methode basierend auf den spezifischen Anforderungen und Einschränkungen Ihres speziellen Problems aus. Hoffentlich wirft dies Licht auf die Konzeptualisierung und Umsetzung der schwer fassbaren Aufgabe, aus einer Reihe von Präfixsummen mit Aktualisierungen eine Untergrenze für K zu finden und dabei die beispiellose Leistungsfähigkeit von Fenwick-Bäumen im C++-Bereich zu nutzen.

Das obige ist der detaillierte Inhalt vonFragen Sie die Untergrenze von K mithilfe des Präfixes und der Array-Aktualisierung des Baumarrays ab. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!