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.
Notez qu’on peut l’adapter pour répondre à des requêtes de minimum d’une plage (cf. range min query sur Wikipédia).
- 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