Arbre indexé binaire : principes fondamentaux et implémentation
La structure d'arbre indexé binaire (Binary Indexed Tree, ou BIT) offre un compromis efficace entre mises à jour ponctuelles et requêtes sur des intervalles, avec une complexité logarithmique. Lorsqu'elle est appliquée à un tableau de différences, elle peut également gérer des modifications d'intervalle avec des requêtes ponctuelles.
Concept ce ...
Publié le 15 juillet à 13h27
Dénombrement de types distincts sur une ligne avec deux arbres de Fenwick
Description technique
On considère une ligne de n positions numérotées de 1 à n. Deux opérations sont disponibles :
Ajouter une nouvelle entité sur l'intervalle fermé [l, r]. Chaque ajout correspond à un type distintc.
Interroger le nombre de types distincts présents dans l'intervalle [l, r].
Le nombre total d'opérations, noté m, est de l'ord ...
Publié le 1 juillet à 22h28