Skip to main content Link Search Menu Expand Document (external link)

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).

Commentaires