Arbre de Fenwick
C’est une structure de données dynamique : elle permet de stocker un tableau de $n$ valeurs et de réaliser efficacement les opérations suivantes :
- mettre à jour une valeur du tableau ;
- calculer la somme d’une plage du tableau.
Update 28 septembre 2024. On peut aussi faire des range add et point query avec peu de modifications. Et on peut faire range add et query sum en ayant deux tels tableaux. Voici plusieurs posts sur le sujet :
- CP Algorithms
- CF: Range sum query without segment tree
- CF: Historic sums
- Un blog post de Petr à ce sujet.
Notez qu’on peut l’adapter pour répondre à des requêtes de minimum d’une plage (cf. range min query sur Wikipédia) mais on préférera peut-être utiliser un segment tree.
- Voir l’article Wikipédia sur les arbres de Fenwick
(on les appelle aussi binary indexed trees) - Voir le code sur TryAlgo Docs
- Voir le code sur GitHub