Interrogez la limite inférieure de K en utilisant le préfixe et la mise à jour du tableau du tableau arborescent

Un tableau de somme de séquence primaire est une collection qui accumule la somme des éléments entrelacés jusqu'à ce qu'un index spécifique soit atteint. Il s'agit d'une stratégie largement utilisée dans le refactoring combinatoire pour optimiser la complexité temporelle. Les tableaux d'arbres, également connus sous le nom d'arbres d'index binaires (BIT), sont une forme de base de données qui met à jour efficacement les éléments et calcule la somme des séquences précédentes en complexité temporelle logarithmique.

Dans cet article, nous verrons comment utiliser Fenwick Tree en C++ avec des améliorations modernes pour révéler la limite la plus petite pour une valeur donnée, appelée K, à partir d'une série de tableaux additionnés.

Grammaire

La syntaxe définit deux fonctions, mise à jour et requête, et une fonction principale pour un arbre Fenwick, une structure de données pour des opérations efficaces de requête et de mise à jour de plage. La fonction de mise à jour accepte un index idx, une valeur val, la taille du tableau n et le tableau d'arborescence Fenwick BIT. Il met à jour l'arborescence Fenwick en ajoutant val au nœud à l'index idx et à tous ses ancêtres. La fonction de requête accepte un index idx et un tableau d'arbres Fenwick BIT. Il renvoie la somme cumulée du nœud racine au nœud avec l'index idx. La fonction principale déclare la taille n du tableau, le préfixe et l'arr du tableau, ainsi que le tableau d'arbres Fenwick BIT initialisé à 0.

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

Algorithme

Pour déterminer la valeur minimale de K dans le préfixe et le tableau avec la mise à jour de l'arbre Fenwick, suivez les étapes complexes ci-dessous -

• Instancier un arbre Fenwick (BIT) de taille n+1, en initialisant tous les éléments à 0.

• Utilisez la fonction update() pour modifier l'arbre Fenwick avec le préfixe et le tableau donnés.

• Exécutez une requête sur l'arbre de Fenwick pour déterminer la borne inférieure de K. Itérer en commençant par le bit le plus significatif dans la représentation binaire de n jusqu'au bit le moins significatif. Utilisez la fonction query() pour vérifier si la somme actuelle des préfixes est inférieure ou égale à K. Si cette condition est remplie, la somme actuelle des préfixes est soustraite de K et l'index est mis à jour pour passer au bit suivant. Si la condition n'est pas remplie, passez au bit suivant sans mettre à jour l'index.

• Après avoir parcouru tous les bits, l'index représentera le préfixe et la limite inférieure de K dans le tableau.

• Sortez l'indice obtenu comme limite inférieure de K.

Méthode

• Méthode 1 - Effectuez une recherche binaire sur l'arbre Fenwick. Dans cette méthode, nous effectuons une recherche binaire sur l’arbre de Fenwick pour trouver la borne inférieure de K.

• Méthode 2 - Recherche binaire avec propagation retardée sur l'arbre Fenwick.

Méthode 1

Pour résoudre ce problème, nous définissons d'abord les pointeurs gauche et droit sur 1 et n respectivement (indiquant la taille du préfixe et du tableau), puis utilisons une stratégie de recherche binaire pour déterminer l'index i correspondant à la plus grande somme de préfixes inférieure à ou égal à K. Ensuite, selon que la valeur de la somme des préfixes [i] est inférieure ou égale à K, la position du pointeur gauche ou du pointeur droit est mise à jour.

Exemple

Le mécanisme de base de ce code consiste à utiliser une structure de données appelée Fenwick Tree (également connue sous le nom d'arbre indexé binaire). Son but est de déterminer la limite inférieure de la valeur spécifiée « k » dans le tableau de somme de préfixes. Ceci est accompli en construisant un arbre Fenwick à l'aide d'une fonction de mise à jour qui fusionne le préfixe et la valeur de chaque élément du tableau dans la position correspondante dans l'arbre Fenwick.

La fonction

findLowerBound utilise ensuite un algorithme de recherche binaire pour connaître la limite inférieure de « k » dans le préfixe et le tableau en interrogeant la fonction. Cette fonction calcule la somme cumulée des valeurs jusqu'à l'index actuel dans l'arbre Fenwick. Finalement, le code finit par identifier le préfixe et l'index de la limite inférieure de "k" dans le tableau, et affiche le résultat sur la console.

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

Sortie

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

Méthode 2

Pour optimiser davantage les arbres Fenwick, une technique appelée propagation paresseuse peut être utilisée. Cette approche implique de différer les mises à jour de l'arbre Fenwick jusqu'à ce qu'elles soient réellement nécessaires, réduisant ainsi le nombre de mises à jour et rendant le processus de requête plus efficace.

Exemple

Le code fournit une solution pour localiser la limite inférieure d'une valeur K donnée dans un tableau de somme de préfixes. Un tableau de somme de préfixes est un tableau dans lequel chaque élément est la somme des éléments de l'index 0 à cet index dans le tableau d'origine. La limite inférieure est le premier index du tableau de somme de préfixes tel que la somme des éléments jusqu'à cet index est égale ou supérieure à K. La solution utilise une structure de données arborescente Fenwick et une technique de propagation de retard pour améliorer l'efficacité de la solution. Le code comprend des fonctions permettant de modifier les arbres de Fenwick, de calculer les sommes de préfixes et de trouver des limites inférieures. Le code initialise également les tableaux de somme de préfixes, les arbres Fenwick et les tableaux à propagation retardée. Enfin, il affiche le préfixe et la limite inférieure de K dans le tableau.

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

Sortie

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.

Conclusion

Discussion sur l'extraction de seuils de valeur K insaisissables à partir de préfixes et de tableaux bien conçus, améliorée par une mise à jour qui exploite l'algorithme intelligent de l'arbre Fenwick du monde de la programmation C++. Plongez dans les complexités de deux méthodes efficaces : la recherche binaire sur les arbres de Fenwick et la recherche binaire sur les arbres de Fenwick avec propagation paresseuse. Choisissez soigneusement la méthode la plus appropriée en fonction des exigences et des contraintes spécifiques de votre problème particulier. Espérons que cela éclaire la conceptualisation et la mise en œuvre de la tâche insaisissable consistant à trouver une limite inférieure sur K à partir d'un ensemble de sommes de préfixes avec des mises à jour, en tirant parti de la puissance inégalée des arbres de Fenwick dans le domaine C++.

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!