Arbre de Fenwick pour les sommes préfixes
Mettre à jour un point et interroger un préfixe en log n
Arbre de Fenwick pour les sommes préfixes est une leçon Competitive Programming Academy gratuite sur CoddyKit. Ceci est la leçon 1 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Competitive Programming Academy, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Competitive Programming Academy comprend 4 leçons au total.
Pourquoi les tableaux de préfixes échouent
Un simple tableau de sommes préfixes répond instantanément aux intervalles, mais une seule mise à jour vous oblige à le reconstruire. Avec de nombreuses mises à jour, cela devient lent. ⏱️
Voici l'arbre de Fenwick
L'arbre de Fenwick, ou BIT, prend en charge les mises à jour ponctuelles et les requêtes de préfixe en O(log n). C'est votre outil privilégié pour les totaux cumulés dynamiques.
Indexation à partir de 1
Un arbre de Fenwick vit dans un tableau indexé à partir de 1. Nous utilisons l'indice 0 comme sentinelle silencieuse, afin que toutes vos données réelles commencent à la position 1.
tree = [0] * (n + 1)La magie du bit de poids faible
Chaque indice couvre un bloc de valeurs. La taille du bloc vaut i & -i, le bit de poids faible de i. Cette seule astuce fait fonctionner tout l'arbre.
lowbit = i & -iMettre à jour un point
Pour ajouter une valeur à la position i, avancez du bit de poids faible à chaque étape et touchez chaque bloc qui contient i.
while i <= n:
tree[i] += delta
i += i & -iInterroger une somme préfixe
Pour additionner les i premières valeurs, reculez en soustrayant le bit de poids faible à chaque étape, jusqu'à atteindre zéro.
s = 0
while i > 0:
s += tree[i]
i -= i & -iLes deux boucles sont logarithmiques
Chaque boucle désactive un bit par itération et s'exécute donc au plus log n fois. C'est pourquoi la mise à jour comme la requête restent rapides.
Somme d'intervalle à partir de deux préfixes
Vous voulez la somme de l à r ? Calculez prefix(r) moins prefix(l-1), comme avec un tableau de préfixes statique, mais les mises à jour sont maintenant rapides elles aussi.
range_sum = query(r) - query(l - 1)Construire l'arbre
La construction la plus simple appelle mise à jour pour chaque valeur initiale. Elle s'exécute en O(n log n) et est largement assez rapide pour la plupart des concours.
for i, v in enumerate(a, 1):
update(i, v)Une empreinte mémoire minuscule
Un arbre de Fenwick n'a besoin que d'un seul tableau de taille n+1. Cette empreinte compacte explique en partie pourquoi il est tant apprécié dans les concours. 💾
Quand choisir un BIT
Choisissez un arbre de Fenwick lorsque vous alternez mises à jour ponctuelles et requêtes de sommes préfixes ou d'intervalles. Il est rapide à coder et difficile à égaler.
Vérification rapide
Voyons précisément comment les boucles se déplacent.
Récapitulatif : notions de base sur BIT
Vous avez découvert l'arbre de Fenwick : indexé à partir de 1, fondé sur i & -i, avec une mise à jour ponctuelle et une requête de préfixe en O(log n). Ensuite, nous l'utiliserons pour compter les inversions. 🎯
Questions Fréquemment Posées
La leçon « Arbre de Fenwick pour les sommes préfixes » est-elle gratuite ?
Oui — le texte complet de « Arbre de Fenwick pour les sommes préfixes » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Competitive Programming Academy, passe à CoddyKit PRO. Le cours Competitive Programming Academy comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Arbre de Fenwick pour les sommes préfixes » ?
Mettre à jour un point et interroger un préfixe en log n Tu pratiques Competitive Programming Academy avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer Competitive Programming Academy ?
Aucune expérience préalable n'est requise. Competitive Programming Academy sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 1 sur 4.
Combien de temps prend la leçon « Arbre de Fenwick pour les sommes préfixes » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon Competitive Programming Academy ?
Oui. Chaque leçon Competitive Programming Academy inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- Arbre de Fenwick pour les sommes préfixes
- Inversions avec un BIT
- Arbre de segments : construction et requêtes
- Propagation paresseuse pour les mises à jour de plages