Calculateur d'indices Fenwick

Un arbre de Fenwick, aussi appelé binary indexed tree, répond aux sommes de préfixe et aux mises à jour ponctuelles en temps logarithmique en stockant des plages partielles dont les longueurs sont des puissances de deux. Chaque pas de navigation repose sur une astuce binaire : le bit de poids faible de l'indice 1-based courant, écrit lsb égal à i AND le négatif de i en complément à deux. Ajouter ce lsb parcourt la chaîne de mise à jour ; le soustraire parcourt la chaîne de requête de préfixe. Étudiants, programmeurs compétitifs et auteurs de bibliothèques ont besoin de ces indices parent et suivant sans redériver les identités sous la pression d'un examen. Ce calculateur d'indices d'arbre de Fenwick accepte un indice positif i et, en option, une taille d'arbre n ; il renvoie le lsb, le suivant de mise à jour et le parent de requête en une étape, des formes binaires pour l'enseignement et, lorsque n est fourni, le chemin complet de mise à jour et de requête du code BIT classique.

Comment les indices de Fenwick utilisent le bit de poids faible

Dans un binary indexed tree à indices 1-based, la cellule d'indice i est responsable d'un segment contigu du tableau sous-jacent dont la longueur égale le bit de poids faible de i. Cette longueur se calcule comme lsb égal à i AND la négation en complément à deux de i, souvent écrit i and minus i dans les langages à arithmétique modulaire sur entiers de largeur fixe.

Géométriquement, inverser tous les bits sous le un de poids le plus faible isole cette puissance de deux ; le ET bit à bit avec l'indice d'origine produit exactement cette puissance. La boucle classique de mise à jour part de l'indice modifié et remplace i par i plus lsb tant que i reste dans la taille n de l'arbre, de sorte que chaque pas saute à l'indice suivant qui doit absorber le delta.

La boucle classique de requête de préfixe part de l'extrémité droite du préfixe et remplace i par i moins lsb tant que i reste positif, en additionnant les cellules responsables qui pavent l'intervalle de un jusqu'à l'indice d'origine. Ensemble, ces deux parcours implémentent des sommes d'intervalle via l'inclusion de deux préfixes.

Comprendre une seule étape—suivant de mise à jour égal à i plus lsb, parent de requête égal à i moins lsb—suffit pour déboguer les erreurs off-by-one, dessiner l'arbre de responsabilités au tableau et vérifier qu'une implémentation correspond aux identités du manuel avant de l'intégrer dans un modèle de concours ou un pipeline analytique de production.

Quand les étapes d'un arbre de Fenwick sont utiles

Les coachs de programmation compétitive et les juges en ligne utilisent un calculateur d'indices d'arbre de Fenwick pour que les apprenants vérifient les pas parent et suivant tout en écrivant à la main les boucles de mise à jour et de requête. Les outils de préparation aux entretiens ont besoin d'un oracle déterministe qui s'accorde avec tout tutoriel BIT standard sur les mêmes entrées entières, y compris les indices gênants qui valent une puissance de deux moins un. Une validation échouée ne consomme pas le solde.

Gardez les indices dans la plage positive sur trente-deux bits, figez les tableaux de chemin dans les tests lorsque size est défini, et vous obtenez une navigation reproductible pour les devoirs, les captures de documentation et les edge workers sans monter votre propre bac à sable complet de structures de données.