Publié · en amélioration
Algorithm
Un arbre de segments répond aux requêtes de somme ou de minimum sur intervalle et aux mises à jour en O(log n) ; l'arbre de Fenwick est sa version légère.
Un arbre de segments est un arbre binaire qui stocke un résumé, comme la somme, le minimum ou le maximum, de chaque intervalle obtenu en coupant un tableau en deux de façon répétée. La racine couvre tout le tableau, chaque feuille couvre un seul élément et chaque nœud interne combine ses deux enfants. Toute question portant sur un intervalle contigu se résout alors en combinant quelques nœuds.
Les sommes préfixes donnent une somme d'intervalle en O(1), mais une seule modification coûte O(n) ; un tableau brut se met à jour instantanément, mais chaque requête coûte O(n). Un arbre de segments traite à la fois les mises à jour ponctuelles et les requêtes d'intervalle en O(log n), ce qui en fait l'outil adapté lorsque les valeurs changent sans cesse et que les requêtes affluent. Avec la propagation paresseuse, il gère aussi les mises à jour d'intervalle, comme ajouter une valeur à toute une plage, en O(log n).
Commencez par comprendre où les sommes préfixes atteignent leurs limites, puis dessinez un petit arbre à la main et suivez les nœuds visités par une requête et par une mise à jour. Écrivez ensuite vous-même la courte version itérative et un arbre de Fenwick, puis entraînez-vous sur des problèmes classiques : minimum sur intervalle, comptage d'inversions, ajout et somme sur intervalle.
Chaque nœud est responsable d'un intervalle du tableau et en stocke la somme ou le minimum ; toute opération associative possédant un élément neutre convient.
Modifier un élément ne recalcule qu'un chemin de la feuille à la racine, et une requête d'intervalle combine au plus deux nœuds par niveau.
Une mise à jour d'intervalle laisse une note sur les nœuds qui la couvrent et ne la transmet aux enfants que lorsqu'une opération doit descendre.
Pour les opérations inversibles comme la somme, un arbre de Fenwick (BIT) atteint la même complexité avec un tableau de n + 1 cases et quelques boucles courtes.
Un arbre de segments itératif : les éléments occupent la seconde moitié d'un tableau de taille 2n et chaque case précédente contient la somme de ses deux enfants. update remonte de la feuille à la racine en recalculant les sommes, et query remonte depuis les deux bornes de l'intervalle semi-ouvert [left, right) en n'ajoutant que les nœuds de bord. Le programme affiche 26, 17 puis 28.
segment_tree.py
class SegmentTree:
"""Iterative segment tree: point update and range sum in O(log n)."""
def __init__(self, values):
self.n = len(values)
self.tree = [0] * self.n + list(values)
for i in range(self.n - 1, 0, -1):
self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]
def update(self, index, value):
i = index + self.n
self.tree[i] = value
while i > 1:
i //= 2
self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]
def query(self, left, right):
"""Sum of values[left:right] (half-open range)."""
total = 0
lo, hi = left + self.n, right + self.n
while lo < hi:
if lo & 1:
total += self.tree[lo]
lo += 1
if hi & 1:
hi -= 1
total += self.tree[hi]
lo //= 2
hi //= 2
return total
if __name__ == "__main__":
tree = SegmentTree([5, 3, 7, 9, 6, 4, 1, 2])
print(tree.query(2, 6)) # 7 + 9 + 6 + 4 = 26
tree.update(3, 0)
print(tree.query(2, 6)) # 7 + 0 + 6 + 4 = 17
print(tree.query(0, 8)) # 28
python segment_tree.pySix chapitres pour aller de l'installation aux notions essentielles de Arbres de segments.
Posez vos questions, partagez votre expérience et échangez vos avis sur Arbres de segments.
Aucune discussion pour l'instant. Lancez la première.
0 commentaire
Se connecter · Connectez-vous pour laisser un commentaire.
Soyez le premier à commenter.