Un arbre de segments et un arbre de Fenwick (Binary Indexed Tree, BIT) répondent tous deux à des requêtes de plage (par exemple, somme sur [l, r]) et à des mises à jour ponctuelles en , comparé à O(n) pour un scan naïf ou O(n) mises à jour pour un tableau de sommes préfixes.
Array + many "sum of range [l,r]" and "update index i" calls:
naive prefix sums: query O(1) but UPDATE is O(n)
segment/Fenwick: query O(log n) AND update O(log n)
class Fenwick:
def __init__(self, n):
self.t = [0]*(n+1)
def update(self, i, delta): # O(log n)
i += 1
while i < len(self.t):
self.t[i] += delta
i += i & (-i) # jump to next responsible node
def prefix(self, i): # sum of [0..i], O(log n)
i += 1; s = 0
while i > 0:
s += self.t[i]
i -= i & (-i)
return s
def range_sum(self, l, r):
return self.prefix(r) - self.prefix(l-1)
Un arbre de segments stocke un agrégat par segment de tableau dans un arbre binaire, supportant n'importe quelle opération associative (somme, min, max, pgcd) et, avec propagation lazy, aussi des mises à jour de plage.
[0..7] sum
/ \
[0..3] [4..7]
/ \ / \
[0..1][2..3] [4..5][6..7] ... down to single elements
| Fenwick (BIT) | Arbre de segments | |
|---|---|---|
| Requête / mise à jour | O(log n) | O(log n) |
| Espace | O(n) | O(2n) |
| Opérations | sommes (inversibles) | n'importe quelle op associative |
| Mises à jour de plage | plus difficile | facile (lazy propagation) |
| Taille du code | minuscule | plus grand |
Ces structures rendent "mettre à jour une valeur, puis interroger un agrégat sur une plage" rapide — essentiel pour la programmation compétitive, les fenêtres d'analyse et les problèmes d'intervalles.
Choisir entre eux est un compromis : un arbre de Fenwick est minuscule et rapide pour les sommes, tandis qu'un arbre de segments est plus flexible pour les charges de travail min/max/mises à jour de plage.