À l'aide d'un tableau arborescent (requête hors ligne), calculez le nombre d'éléments supérieurs à K dans la plage L à R

Dans le domaine de l'informatique, nous devons traiter de grands ensembles de données qui incluent des opérations de sélection et de mise à jour de requêtes. Effectuer ces opérations en temps réel avec une faible complexité temporelle est une tâche difficile pour les développeurs.

L'utilisation d'arbres Fenwick est un moyen efficace de résoudre ces problèmes de requêtes basées sur des plages.

Fenwick Tree est une structure de données qui peut mettre à jour efficacement les éléments et calculer la somme des préfixes des nombres dans un tableau. On l’appelle également arbre d’index binaire.

Dans cet article, nous verrons comment trouver le nombre d'éléments supérieur à K dans la plage L à R à l'aide de l'arbre de Fenwick.

Scénarios d'entrée et de sortie

Supposons que vous ayez un tableau avec N éléments et que vous souhaitiez trouver le nombre d'éléments du tableau qui sont supérieurs à K dans la plage L à R.

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

Qu'est-ce qu'une requête hors ligne ?

La requête hors ligne est une opération de requête effectuée sur un ensemble de données prédéterminé. En d’autres termes, ces opérations sont effectuées uniquement sur les ensembles de données qui ne sont pas modifiés lors du traitement de la requête.

Utilisation de l'arbre Fenwick

Ici, nous utiliserons un arbre de Fenwick, qui a des vecteurs à chaque nœud contenant tous les éléments du tableau dans l'ordre. Nous utilisons ensuite la recherche binaire pour répondre à chaque requête et compter le nombre d'éléments.

• Créez deux fonctions, updateTree() et total(), pour mettre à jour et récupérer la somme du préfixe dans BIT respectivement.

• Ensuite, créez une autre fonction qui comptera les éléments compris entre L et R qui sont supérieurs à "K". Cette fonction accepte les valeurs d'entrée "arr", "N", "L", "R" et "K".

• Le décompte est calculé en soustrayant la somme cumulée de K de la somme cumulée de la plage maximale N.

Pour exclure les éléments hors plage, soustrayez la somme cumulée de L-1 (si L est supérieur à 1).

Exemple

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

Sortie

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

Méthode alternative

Ici, nous allons créer un vecteur séparé pour stocker la requête. Chaque requête se compose de deux variables, index et val. index est utilisé pour stocker la position dans le tableau, tandis que val est utilisé pour stocker la valeur de l'élément à cet index. Cette approche permet aux développeurs d'effectuer diverses opérations de requête. De plus, nous utilisons BIT pour compter le nombre d'éléments supérieurs à K pour chaque requête.

Exemple

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

Sortie

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

Conclusion

Nous pouvons simplement parcourir le tableau de l'index L à R et ajouter 1 à chaque fois que l'élément du tableau est supérieur à K afin de trouver la réponse à chaque requête. Cependant, afin de réduire la complexité temporelle, nous utilisons Arbre de Fenwick pour effectuer de telles opérations de requête. Nous pouvons également utiliser Line Segment Tree et Sparse Table au lieu de l'arbre Fenwick pour effectuer de telles opérations de requête.

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!