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
Arbre de Fenwick
Introduction
L'arbre de Fenwick est une structure de données efficace pour gérer les sommes préfixes. Il offre des opérations rapides de mise à jour et de requête avec une complexité logarithmique.
Fonction lowbit
L'opération fondamentale lowbit(x) = x & -x isole le bit le plus bas à 1 dans la représantation binaire d'un nombre.
Principe de ...
Publié le 8 juin à 00h10