Rilasciato · in miglioramento
Algorithm
Un albero di segmenti risponde a query di somma o minimo su intervallo e aggiorna i valori in O(log n); l'albero di Fenwick è la variante leggera per le somme.
Un albero di segmenti è un albero binario che memorizza un riepilogo, come somma, minimo o massimo, di ogni intervallo ottenuto dividendo ripetutamente a metà un array. La radice copre l'intero array, ogni foglia copre un solo elemento e ogni nodo interno combina i suoi due figli. Così qualsiasi domanda su un intervallo contiguo si risolve combinando pochi nodi.
Le somme prefisse danno la somma di un intervallo in O(1), ma richiedono O(n) per assorbire una sola modifica; un array semplice si aggiorna subito, ma ogni query costa O(n). Un albero di segmenti gestisce sia gli aggiornamenti puntuali sia le query su intervallo in O(log n), ed è quindi lo strumento giusto quando i valori cambiano di continuo e le domande sugli intervalli continuano ad arrivare. Con la propagazione lazy supporta anche aggiornamenti su intervallo, come sommare un valore a un intero tratto, in O(log n).
Conviene partire dai limiti delle somme prefisse, disegnare a mano un piccolo albero e seguire quali nodi tocca una query e quali un aggiornamento. Poi scrivi da solo la breve implementazione iterativa e un albero di Fenwick, ed esercitati su problemi classici come minimo su intervallo, conteggio delle inversioni e somma su intervallo con aggiornamenti su intervallo.
Ogni nodo è responsabile di un intervallo dell'array e ne memorizza somma o minimo; qualsiasi operazione associativa con elemento neutro si adatta alla stessa struttura.
Modificare un elemento ricalcola un solo percorso dalla foglia alla radice, e una query su intervallo combina al massimo due nodi per livello.
Un aggiornamento su intervallo lascia una nota sui nodi che lo coprono e la passa ai figli solo quando un'operazione deve scendere.
Per operazioni invertibili come la somma, un albero di Fenwick (BIT) ottiene la stessa complessità con un array di n + 1 celle e pochi cicli brevi.
Un albero di segmenti iterativo: gli elementi stanno nella seconda metà di un array di dimensione 2n e ogni posizione precedente contiene la somma dei suoi due figli. update risale dalla foglia alla radice ricalcolando le somme, e query risale dai due estremi dell'intervallo semiaperto [left, right) sommando solo i nodi di bordo. L'esecuzione stampa 26, 17 e 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.pySei capitoli che ti accompagnano dall'installazione ai concetti chiave di Alberi di segmenti.
Fai domande, condividi la tua esperienza e scambia opinioni su Alberi di segmenti.
Ancora nessuna discussione. Avvia la prima.
0 commenti
Accedi · Accedi per lasciare un commento.
Scrivi tu il primo commento.