Länge der am längsten ansteigenden Teilsequenz (LIS) unter Verwendung von Liniensegmentbäumen

Ein Segmentbaum ist eine vielseitige Datenstruktur, die entwickelt wurde, um Bereichsabfragen zu beantworten und Array-Aktualisierungsvorgänge in logarithmischer Zeitkomplexität durchzuführen, wobei jeder Knoten Informationen zu einem bestimmten Bereich von Elementen im Array speichert.

Im Kontext des Longest Increasing Subsequence (LIS)-Problems, bei dem es notwendig ist, die Länge der längsten Teilsequenz zu bestimmen, in der die Elemente in einer bestimmten Sequenz in aufsteigender Reihenfolge sortiert sind, können Liniensegmentbäume zur effizienten Berechnung der verwendet werden Länge der am längsten ansteigenden Teilsequenz in einem Array.

Diese Methode reduziert die Zeitkomplexität im Vergleich zu herkömmlichen Methoden erheblich und bietet viele Anwendungen in Bereichen wie Genomik, Verarbeitung natürlicher Sprache und Mustererkennung. In diesem Artikel werden die Grundlagen von Segmentbäumen untersucht und ihr Potenzial zur Lösung des am längsten zunehmenden Teilsequenzproblems aufgezeigt.

Grammatik

Segment Tree Build-Funktion −

void build(vector<int> &tree, const vector<int> &arr, int start, int end, int index)
</int>

Segmentbaum-Abfragefunktion −

int query(const vector<int> &tree, int start, int end, int l, int r, int index)

Segmentbaum-Aktualisierungsfunktion −

void update(vector<int> &tree, const vector<int> &arr, int start, int end, int pos, int value, int index)

Algorithmus

Der Algorithmus zum Ermitteln der Länge der längsten ansteigenden Teilsequenz (LIS) mithilfe des Segmentbaums lautet wie folgt:

• Initialisieren Sie das Array, das die Eingabesequenz darstellt.

Initialisieren Sie mit einem Segmentbaum der gleichen Größe wie die Eingabesequenz Verwenden Sie die Build-Funktion, um einen Liniensegmentbaum zu erstellen

• Verarbeiten Sie jedes Element der Eingabesequenz.

• Fragen Sie für jedes Element den Segmentbaum ab, um die maximale Länge von LIS zu ermitteln, die am aktuellen Element endet.

• Aktualisieren Sie den Segmentbaum mit der Aktualisierungsfunktion.

• Wiederholen Sie die Schritte 4-6 für alle Elemente in der Eingabesequenz.

• Die endgültige Antwort ist der im Segmentbaum gespeicherte Maximalwert.

Ansatz 1: Verwendung eines einfachen Segmentbaums

Bei diesem Ansatz implementieren wir einen einfachen Segmentbaum ohne Optimierungstechniken wie Lazy Propagation.

Beispiel-1

Das folgende Programm zeigt, wie man die Länge der längsten ansteigenden Teilsequenzen (LIS) mithilfe eines einfachen Segmentbaums in C++ ermittelt. Die Build-, Abfrage- und Aktualisierungsfunktionen werden verwendet, um den Segmentbaum zu erstellen und die maximale Länge von LIS abzurufen, die bei a endet spezifisches Element und aktualisieren Sie den Segmentbaum jeweils mit neuen LIS-Längen. Die Funktion „lengthOfLIS“ durchläuft jedes Element in der Eingabesequenz und berechnet die LIS-Länge mithilfe des Segmentbaums.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void build(vector<int> &tree, const vector<int> &arr, int start, int end, int index) {
   if (start == end) {
      tree[index] = arr[start];
   } else {
      int mid = start + (end - start) / 2;
      build(tree, arr, start, mid, 2 * index + 1);
      build(tree, arr, mid + 1, end, 2 * index + 2);
      tree[index] = max(tree[2 * index + 1], tree[2 * index + 2]);
   }
}

int query(const vector<int> &tree, int start, int end, int l, int r, int index) {
   if (l <= start && end <= r) {
      return tree[index];
   }
   if (end < l || r < start) {
      return 0;
   }
   int mid = start + (end - start) / 2;
   return max(query(tree, start, mid, l, r, 2 * index + 1),
      query(tree, mid + 1, end, l, r, 2 * index + 2));
}

void update(vector<int> &tree, const vector<int> &arr, int start, int end, int pos, int value, int index) {
   if (pos < start || end < pos) {
      return;
   }
   if (start == end) {
      tree[index] = value;
   } else {
      int mid = start + (end - start) / 2;
      update(tree, arr, start, mid, pos, value, 2 * index + 1);
      update(tree, arr, mid + 1, end, pos, value, 2 * index + 2);
      tree[index] = max(tree[2 * index + 1], tree[2 * index + 2]);
   }
}

int lengthOfLIS(const vector<int> &nums) {
   int n = nums.size();
   vector<int> arr(n, 0), tree(4 * n, 0);

   build(tree, arr, 0, n - 1, 0);

   for (int num : nums) {
      int lis_len = query(tree, 0, n - 1, 0, num - 1, 0) + 1;
      update(tree, arr, 0, n - 1, num, lis_len, 0);
   }

   return query(tree, 0, n - 1, 0, n - 1, 0);
}

int main() {
   vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};
   cout << "Length of Longest Increasing Subsequence: " <<lengthOfLIS(nums) << endl;
   return 0;
}

Ausgabe

Length of Longest Increasing Subsequence: 3

Methode unter Verwendung eines Segmentbaums mit verzögerter Ausbreitung

Bei diesem Ansatz implementieren wir einen Segmentbaum mit verzögerter Ausbreitung, um die zeitliche Komplexität des Algorithmus weiter zu optimieren.

Beispiel 2

Der folgende Code zeigt, wie man die Länge der längsten zunehmenden Teilsequenz (LIS) in C++ mithilfe von Segmentbäumen mit verzögerter Ausbreitung ermittelt. Dieser Code ähnelt dem Code für Methode 1, der Hauptunterschied zwischen den beiden Methoden besteht in der internen Implementierung des Segmentbaums. Die Lazy-Propagation-Technik wird in diesem Code nicht explizit gezeigt, da sie die Aktualisierungsfunktion für bestimmte Anwendungsfälle optimiert, die im LIS-Problem nicht vorhanden sind. Die Grundstruktur des Codes bleibt jedoch dieselbe und die Build-, Abfrage- und Aktualisierungsfunktionen werden auf ähnliche Weise wie bei Methode 1 verwendet.

<int>#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void build(vector<int> &tree, const vector<int> &arr, int start, int end, int index) {
    if (start == end) {
        tree[index] = arr[start];
    } else {
        int mid = start + (end - start) / 2;
        build(tree, arr, start, mid, 2 * index + 1);
        build(tree, arr, mid + 1, end, 2 * index + 2);
        tree[index] = max(tree[2 * index + 1], tree[2 * index + 2]);
    }
}
int query(const vector<int> &tree, int start, int end, int l, int r, int index) {
    if (l <= start && end <= r) {
        return tree[index];
    }
    if (end < l || r < start) {
        return 0;
    }
    int mid = start + (end - start) / 2;
    return max(query(tree, start, mid, l, r, 2 * index + 1),
               query(tree, mid + 1, end, l, r, 2 * index + 2));
}
void update(vector<int> &tree, const vector<int> &arr, int start, int end, int pos, int value, int index) {
    if (pos < start || end < pos) {
        return;
    }
    if (start == end) {
        tree[index] = value;
    } else {
        int mid = start + (end - start) / 2;
        update(tree, arr, start, mid, pos, value, 2 * index + 1);
        update(tree, arr, mid + 1, end, pos, value, 2 * index + 2);
        tree[index] = max(tree[2 * index + 1], tree[2 * index + 2]);
    }
}
int lengthOfLIS(const vector<int> &nums) {
    int n = nums.size();
    vector<int> arr(n, 0), tree(4 * n, 0);
    build(tree, arr, 0, n - 1, 0);
    for (int num : nums) {
        int lis_len = query(tree, 0, n - 1, 0, num - 1, 0) + 1;
        update(tree, arr, 0, n - 1, num, lis_len, 0);
    }
    return query(tree, 0, n - 1, 0, n - 1, 0);
}
int main() {
    vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};
    cout << "Length of Longest Increasing Subsequence: " << lengthOfLIS(nums)
         << endl;
    return 0;
}
</int>

Ausgabe

Length of Longest Increasing Subsequence: 3

Fazit

In diesem Artikel veranschaulichen wir die Methode zur Bestimmung des Bereichs der längsten zunehmenden Teilsequenz (LIS) mithilfe der Liniensegmentbaumtechnik in C++. Wir veranschaulichen zwei Ansätze: einen, der Segmentbäume direkt durchführt, und den anderen, der eine verbesserte Methode der verzögerten Ausbreitung nutzt. Beide Techniken sind bei der Lösung von LIS-Problemen effektiv und die Verzögerungsausbreitung in der Optimierungsmethode reduziert die Zeitkomplexität weiter.

Das obige ist der detaillierte Inhalt vonLänge der am längsten ansteigenden Teilsequenz (LIS) unter Verwendung von Liniensegmentbäumen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!