Table des matières
Scénarios d'entrée et de sortie
Qu'est-ce qu'une requête hors ligne ?
Utilisation de l'arbre Fenwick
Exemple
Sortie
Méthode alternative
Conclusion
Maison développement back-end C++ À l'aide d'un tableau arborescent (requête hors ligne), calculez le nombre d'éléments supérieurs à K dans la plage L à R

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

Sep 02, 2023 am 09:05 AM
Requête hors ligne tableau arborescent Nombre d'éléments

À laide dun 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
Copier après la connexion

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;
}
Copier après la connexion

Sortie

Number of elements greater than 4 in the range [1, 8]: 5
Copier après la connexion

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;
}
Copier après la connexion

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
Copier après la connexion

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!

Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn

Outils d'IA chauds

Undresser.AI Undress

Undresser.AI Undress

Application basée sur l'IA pour créer des photos de nu réalistes

AI Clothes Remover

AI Clothes Remover

Outil d'IA en ligne pour supprimer les vêtements des photos.

Undress AI Tool

Undress AI Tool

Images de déshabillage gratuites

Clothoff.io

Clothoff.io

Dissolvant de vêtements AI

AI Hentai Generator

AI Hentai Generator

Générez AI Hentai gratuitement.

Article chaud

R.E.P.O. Crystals d'énergie expliqués et ce qu'ils font (cristal jaune)
1 Il y a quelques mois By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. Meilleurs paramètres graphiques
1 Il y a quelques mois By 尊渡假赌尊渡假赌尊渡假赌
Will R.E.P.O. Vous avez un jeu croisé?
1 Il y a quelques mois By 尊渡假赌尊渡假赌尊渡假赌

Outils chauds

Bloc-notes++7.3.1

Bloc-notes++7.3.1

Éditeur de code facile à utiliser et gratuit

SublimeText3 version chinoise

SublimeText3 version chinoise

Version chinoise, très simple à utiliser

Envoyer Studio 13.0.1

Envoyer Studio 13.0.1

Puissant environnement de développement intégré PHP

Dreamweaver CS6

Dreamweaver CS6

Outils de développement Web visuel

SublimeText3 version Mac

SublimeText3 version Mac

Logiciel d'édition de code au niveau de Dieu (SublimeText3)

C Structure des données du langage: représentation des données et fonctionnement des arbres et des graphiques C Structure des données du langage: représentation des données et fonctionnement des arbres et des graphiques Apr 04, 2025 am 11:18 AM

C Structure des données du langage: La représentation des données de l'arborescence et du graphique est une structure de données hiérarchique composée de nœuds. Chaque nœud contient un élément de données et un pointeur vers ses nœuds enfants. L'arbre binaire est un type spécial d'arbre. Chaque nœud a au plus deux nœuds enfants. Les données représentent StrustReenode {intdata; structTreenode * gauche; structureReode * droite;}; L'opération crée une arborescence d'arborescence arborescence (prédécision, ordre dans l'ordre et ordre ultérieur) Le nœud d'insertion de l'arborescence des arbres de recherche de nœud Graph est une collection de structures de données, où les éléments sont des sommets, et ils peuvent être connectés ensemble via des bords avec des données droites ou peu nombreuses représentant des voisins.

La vérité derrière le problème de fonctionnement du fichier de langue C La vérité derrière le problème de fonctionnement du fichier de langue C Apr 04, 2025 am 11:24 AM

La vérité sur les problèmes de fonctionnement des fichiers: l'ouverture des fichiers a échoué: les autorisations insuffisantes, les mauvais chemins de mauvais et les fichiers occupés. L'écriture de données a échoué: le tampon est plein, le fichier n'est pas écrivatif et l'espace disque est insuffisant. Autres FAQ: traversée de fichiers lents, encodage de fichiers texte incorrect et erreurs de lecture de fichiers binaires.

Comment utiliser efficacement les références RValue en C? Comment utiliser efficacement les références RValue en C? Mar 18, 2025 pm 03:29 PM

L'article discute de l'utilisation efficace des références de référence en C pour la sémantique de déplacement, le transfert parfait et la gestion des ressources, mettant en évidence les meilleures pratiques et les améliorations des performances. (159 caractères)

Comment calculer C-SUBScript 3 Indice 5 C-SUBScript 3 Indice Indice 5 Tutoriel d'algorithme Comment calculer C-SUBScript 3 Indice 5 C-SUBScript 3 Indice Indice 5 Tutoriel d'algorithme Apr 03, 2025 pm 10:33 PM

Le calcul de C35 est essentiellement des mathématiques combinatoires, représentant le nombre de combinaisons sélectionnées parmi 3 des 5 éléments. La formule de calcul est C53 = 5! / (3! * 2!), Qui peut être directement calculé par des boucles pour améliorer l'efficacité et éviter le débordement. De plus, la compréhension de la nature des combinaisons et la maîtrise des méthodes de calcul efficaces est cruciale pour résoudre de nombreux problèmes dans les domaines des statistiques de probabilité, de la cryptographie, de la conception d'algorithmes, etc.

Comment utiliser Move Semantics en C pour améliorer les performances? Comment utiliser Move Semantics en C pour améliorer les performances? Mar 18, 2025 pm 03:27 PM

L'article discute de l'utilisation de Move Semantics en C pour améliorer les performances en évitant la copie inutile. Il couvre la mise en œuvre de constructeurs de déplace

Quelles sont les exigences de base pour les fonctions de langue C Quelles sont les exigences de base pour les fonctions de langue C Apr 03, 2025 pm 10:06 PM

Les fonctions de langue C sont la base de la modularisation du code et de la construction de programmes. Ils se composent de déclarations (en-têtes de fonction) et de définitions (corps de fonction). Le langage C utilise des valeurs pour transmettre les paramètres par défaut, mais les variables externes peuvent également être modifiées à l'aide d'adresse Pass. Les fonctions peuvent avoir ou ne pas avoir de valeur de retour et le type de valeur de retour doit être cohérent avec la déclaration. La dénomination de la fonction doit être claire et facile à comprendre, en utilisant un chameau ou une nomenclature de soulignement. Suivez le principe de responsabilité unique et gardez la simplicité de la fonction pour améliorer la maintenabilité et la lisibilité.

Définition du nom de la fonction dans le langage C Définition du nom de la fonction dans le langage C Apr 03, 2025 pm 10:03 PM

La définition du nom de fonction du langage C comprend: Type de valeur de retour, nom de fonction, liste de paramètres et corps de fonction. Les noms de fonction doivent être clairs, concis et unifiés dans le style pour éviter les conflits avec les mots clés. Les noms de fonction ont des lunettes et peuvent être utilisés après la déclaration. Les pointeurs de fonction permettent de passer des fonctions ou d'attribuer des arguments. Les erreurs communes incluent les conflits de dénomination, l'inadéquation des types de paramètres et les fonctions non déclarées. L'optimisation des performances se concentre sur la conception et la mise en œuvre des fonctions, tandis que le code clair et facile à lire est crucial.

Concept de fonction de langue C Concept de fonction de langue C Apr 03, 2025 pm 10:09 PM

Les fonctions de langue C sont des blocs de code réutilisables. Ils reçoivent des entrées, effectuent des opérations et renvoient les résultats, ce qui améliore modulairement la réutilisabilité et réduit la complexité. Le mécanisme interne de la fonction comprend le passage des paramètres, l'exécution de la fonction et les valeurs de retour. L'ensemble du processus implique une optimisation telle que la fonction en ligne. Une bonne fonction est écrite en suivant le principe de responsabilité unique, un petit nombre de paramètres, des spécifications de dénomination et une gestion des erreurs. Les pointeurs combinés avec des fonctions peuvent atteindre des fonctions plus puissantes, telles que la modification des valeurs de variables externes. Les pointeurs de fonctions passent les fonctions comme des paramètres ou des adresses de magasin, et sont utilisées pour implémenter les appels dynamiques aux fonctions. Comprendre les fonctionnalités et les techniques des fonctions est la clé pour écrire des programmes C efficaces, maintenables et faciles à comprendre.

See all articles