Longueur de la sous-séquence croissante la plus longue (LIS) à l'aide d'arbres de segments de ligne

Un arbre de segments est une structure de données polyvalente conçue pour répondre aux requêtes de plage et effectuer des opérations de mise à jour de tableau dans une complexité temporelle logarithmique, où chaque nœud stocke des informations liées à une plage spécifique d'éléments du tableau.

Dans le contexte du problème de la sous-séquence croissante la plus longue (LIS), où il est nécessaire de déterminer la longueur de la sous-séquence la plus longue dans laquelle les éléments d'une séquence donnée sont triés par ordre croissant, les arbres de segments de droite peuvent être utilisés pour calculer efficacement la longueur de la sous-séquence croissante la plus longue dans un tableau.

Cette méthode réduit considérablement la complexité temporelle par rapport aux méthodes traditionnelles et a de nombreuses applications dans des domaines tels que la génomique, le traitement du langage naturel et la reconnaissance de formes. Cet article explore les principes fondamentaux des arbres de segments et démontre leur potentiel dans la résolution du problème de sous-séquence croissante la plus longue.

Grammaire

Fonction de construction d'arborescence de segments −

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

Fonction de requête d'arborescence de segments −

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

Fonction de mise à jour de l'arborescence des segments −

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

Algorithme

L'algorithme pour trouver la longueur de la sous-séquence croissante (LIS) la plus longue à l'aide d'un arbre de segments est le suivant -

• Initialisez le tableau représentant la séquence d'entrée.

Initialiser avec un arbre de segments de la même taille que la séquence d'entrée Utilisez la fonction build pour créer une arborescence de segments de ligne

• Traitez chaque élément de la séquence d'entrée.

• Pour chaque élément, interrogez l'arborescence de segments pour trouver la longueur maximale du LIS se terminant à l'élément actuel.

• Mettez à jour l'arborescence des segments à l'aide de la fonction de mise à jour.

• Répétez les étapes 4 à 6 pour tous les éléments de la séquence de saisie.

• La réponse finale est la valeur maximale stockée dans l'arborescence des segments.

Approche 1 : Utiliser une arborescence de segments simple

Dans cette approche, nous implémentons un simple arbre de segments sans aucune technique d'optimisation telle que la propagation paresseuse.

Exemple-1

Le programme ci-dessous montre comment trouver la longueur des sous-séquences croissantes (LIS) les plus longues à l'aide d'un simple arbre de segments en C++. Les fonctions de construction, de requête et de mise à jour sont utilisées pour construire l'arbre de segments et récupérer la longueur maximale du LIS se terminant par un. élément spécifique et mettez à jour l'arborescence de segments avec de nouvelles longueurs LIS, respectivement. La fonction lengthOfLIS parcourt chaque élément de la séquence d'entrée et calcule la longueur LIS à l'aide de l'arborescence de segments.

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

Sortie

Length of Longest Increasing Subsequence: 3

Méthode utilisant un arbre à segments à propagation retardée

Dans cette approche, nous implémentons un arbre de segments avec propagation paresseuse pour optimiser davantage la complexité temporelle de l'algorithme.

Exemple 2

Le code ci-dessous montre comment trouver la longueur de la sous-séquence croissante (LIS) la plus longue en C++ à l'aide d'arbres de segments à propagation retardée. Ce code est similaire au code de la méthode 1, la principale différence entre les deux méthodes est l'implémentation interne de l'arborescence des segments. La technique de propagation paresseuse n'est pas explicitement présentée dans ce code car elle optimise la fonction de mise à jour pour des cas d'utilisation spécifiques qui n'existent pas dans le problème LIS. Cependant, la structure de base du code reste la même et les fonctions de génération, de requête et de mise à jour sont utilisées de la même manière que la méthode 1.

<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>

Sortie

Length of Longest Increasing Subsequence: 3

Conclusion

Dans cet article, nous illustrons la méthode de détermination de la plage de la sous-séquence croissante la plus longue (LIS) grâce à la technique de l'arbre de segment de ligne en C++. Nous illustrons deux approches : l'une qui réalise directement des arbres de segments, et l'autre qui exploite une méthode améliorée de propagation retardée. Les deux techniques sont efficaces pour résoudre les problèmes de LIS, et la propagation du retard dans la méthode d'optimisation réduit encore davantage la complexité temporelle.

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!