data-structures
Albero del segmento
Ricerca…
Introduzione all'albero del segmento
Supponiamo di avere una matrice:
+-------+-----+-----+-----+-----+-----+-----+
| Index | 0 | 1 | 2 | 3 | 4 | 5 |
+-------+-----+-----+-----+-----+-----+-----+
| Value | -1 | 3 | 4 | 0 | 2 | 1 |
+-------+-----+-----+-----+-----+-----+-----+
Vogliamo eseguire alcune query su questo array. Per esempio:
- Qual è il minimo da index- 2 a index- 4 ? -> 0
- Qual è il massimo da index- 0 a index- 3 ? -> 4
- Qual è la somma da index- 1 a index- 5 ? -> 10
Come lo scopriamo?
Forza bruta:
Potremmo attraversare la matrice dall'indice di partenza all'indice di finitura e rispondere alla nostra query. In questo approccio, ogni query richiede O(n)
tempo in cui n è la differenza tra l'indice iniziale e l'indice di finitura. Ma cosa succede se ci sono milioni di numeri e milioni di query? Per le domande m , ci vorrebbe O(mn)
tempo. Quindi, per i valori 10⁵ nel nostro array, se eseguiamo query 10⁵, nel caso peggiore, dovremo attraversare 10¹⁰ elementi.
Programmazione dinamica:
Possiamo creare una matrice 6X6 per memorizzare i valori per diversi intervalli. Per l'intervallo minimo di query (RMQ), il nostro array sarebbe simile a:
0 1 2 3 4 5
+-----+-----+-----+-----+-----+-----+-----+
| | -1 | 3 | 4 | 0 | 2 | 1 |
+-----+-----+-----+-----+-----+-----+-----+
0 | -1 | -1 | -1 | -1 | -1 | -1 | -1 |
+-----+-----+-----+-----+-----+-----+-----+
1 | 3 | | 3 | 3 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+
2 | 4 | | | 4 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+
3 | 0 | | | | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+
4 | 2 | | | | | 2 | 1 |
+-----+-----+-----+-----+-----+-----+-----+
5 | 1 | | | | | | 1 |
+-----+-----+-----+-----+-----+-----+-----+
Una volta creata questa matrice, sarebbe sufficiente rispondere a tutti gli RMQ. Qui, Matrix [i] [j] memorizzerebbe il valore minimo da index- i a index- j . Ad esempio: Il minimo da index- 2 a index- 4 è Matrix [2] [4] = 0 . Questa matrice risponde alla query in tempo O(1)
, ma impiega O (n²) per costruire questa matrice e O(n²)
per memorizzarla. Quindi, se n è un numero veramente grande, questo non si adatta molto bene.
Albero del segmento:
Un albero del segmento è una struttura di dati dell'albero per la memorizzazione di intervalli o segmenti. Permette di interrogare quale dei segmenti memorizzati contiene un determinato punto. Ci vuole O(n)
tempo per costruire un albero del segmento, ci vuole O(n)
spazio per mantenerlo e risponde a una query nel tempo O(logn)
.
L'albero del segmento è un albero binario e gli elementi dell'array dato saranno le foglie di quell'albero. Creeremo l'albero del segmento dividendo l'array a metà fino a raggiungere un singolo elemento. Quindi la nostra divisione ci fornirà:
Ora se sostituiamo i nodi non foglia con il valore minimo delle loro foglie, otteniamo:
Quindi questo è il nostro albero del segmento. Possiamo notare che il nodo radice contiene il valore minimo dell'intero array (intervallo [0,5]), il suo figlio sinistro contiene il valore minimo dell'array sinistro (intervallo [0,2]), il figlio destro contiene il minimo valore della nostra matrice giusta (intervallo [3,5]) e così via. I nodi foglia contengono il valore minimo di ogni singolo punto. Noi abbiamo:
Ora facciamo una query di intervallo su questo albero. Per eseguire una query di intervallo, dobbiamo verificare tre condizioni:
- Sovrapposizione parziale: controlliamo entrambe le foglie.
- Sovrapposizione totale: restituiamo il valore memorizzato nel nodo.
- Nessuna sovrapposizione: restituiamo un valore molto grande o infinito.
Diciamo che vogliamo controllare l'intervallo [2,4] , il che significa che vogliamo trovare il minimo da index- 2 a 4 . Inizieremo dalla radice e controlleremo se l'intervallo nei nostri nodi è sovrapposto o meno all'intervallo di query. Qui,
- [2,4] non si sovrappone completamente [0,5] . Quindi controlleremo entrambe le direzioni.
- Al sottostruttura di sinistra, [2,4] si sovrappone parzialmente [0,2] . Controlleremo entrambe le direzioni.
- Al sottoalbero sinistro, [2,4] non si sovrappone [0,1] , quindi questo non contribuirà alla nostra risposta. Restituiamo l' infinito .
- Al sottoalbero destro, [2,4] si sovrappone totalmente [2,2] . Ritorniamo 4 .
Il minimo di questi due valori restituiti (4, infinito) è 4 . Otteniamo 4 da questa parte.
- Al sottoalbero destro, [2,4] si sovrappone parzialmente. Quindi controlleremo entrambe le direzioni.
- Al sottoalbero sinistro, [2,4] si sovrappone completamente [3,4] . Restituiamo 0 .
- Al sottoalbero destro, [2,4] non si sovrappone [5,5] . Restituiamo l' infinito .
Il minimo di questi due valori restituiti (0, infinito) è 0 . Otteniamo 0 da questa parte.
- Al sottostruttura di sinistra, [2,4] si sovrappone parzialmente [0,2] . Controlleremo entrambe le direzioni.
- Il minimo dei valori restituiti (4,0) è 0 . Questo è il nostro intervallo minimo desiderato [2,4] .
Ora possiamo verificare che, a prescindere dalla nostra query, ci vorranno almeno 4 passaggi per trovare il valore desiderato da questo albero del segmento.
Uso:
- Intervallo Query minima
- Il più basso antenato comune
- Propagazione pigra
- Somma sottostringa dinamica
- Trascurare e Min
- Dual Fields
- Trovare il k-esimo elemento più piccolo
- Trovare il numero di coppie non ordinate
Implementazione della struttura del segmento tramite l'array
Diciamo che abbiamo un array: Item = {-1, 0, 3, 6}
. Vogliamo costruire l' array SegmentTree per scoprire il valore minimo in un determinato intervallo. Il nostro segmento di albero sarà simile a:
I numeri sotto i nodi mostrano gli indici di ciascun valore che verranno memorizzati nel nostro array Segmentazione . Possiamo vedere che, per memorizzare 4 elementi, avevamo bisogno di una matrice di dimensione 7. Questo valore è determinato da:
Procedure DetermineArraySize(Item):
multiplier := 1
n := Item.size
while multiplier < n
multiplier := multiplier * 2
end while
size := (2 * multiplier) - 1
Return size
Quindi, se avessimo una matrice di lunghezza 5, la dimensione della nostra matrice Segmentazione sarebbe: ( 8 * 2 ) - 1 = 15 . Ora, per determinare la posizione del figlio sinistro e destro di un nodo, se un nodo è in indice i , allora la posizione del suo:
- Left Child è denotato da: (2 * i) + 1 .
- Right Child è denotato da: (2 * i) + 2 .
E l'indice del genitore di qualsiasi nodo nell'indice i può essere determinato da: (i - 1) / 2 .
Quindi l'array SegmentTree che rappresenta il nostro esempio sarà simile a:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+
| -1 | -1 | 3 | -1 | 0 | 3 | 6 |
+-----+-----+-----+-----+-----+-----+-----+
Diamo un'occhiata allo pseudo-codice per costruire questo array:
Procedure ConstructTree(Item, SegmentTree, low, high, position):
if low is equal to high
SegmentTree[position] := Item[low]
else
mid := (low+high)/2
constructTree(Item, SegmentTree, low, mid, 2*position+1)
constructTree(Item, SegmentTree, mid+1, high, 2*position+2)
SegmentTree[position] := min(SegmentTree[2*position+1], SegmentTree[2*position+2])
end if
Inizialmente, prendiamo l'input dei valori e inizializziamo l'array Segmentree con infinity
usando la lunghezza della matrice Item come dimensione. Chiamiamo la procedura usando:
- basso = indice iniziale dell'array oggetto .
- alta = finitura indice dell'array articolo.
- posizione = 0, indica la radice della nostra struttura del segmento.
Ora proviamo a capire la procedura usando un esempio:
La dimensione del nostro array Item è 4 . Creiamo una serie di lunghezze (4 * 2) - 1 = 7 e inizializzate con infinity
. Puoi usare un valore molto grande per questo. Il nostro array sarebbe simile a:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+
| inf | inf | inf | inf | inf | inf | inf |
+-----+-----+-----+-----+-----+-----+-----+
Poiché si tratta di una procedura ricorsiva, vedremo l'operazione di ConstructTree
utilizzando una tabella di ricorsività che tiene traccia di low
, high
, position
, mid
e calling line
a ogni chiamata. Inizialmente chiamiamo ConstructTree (Item, SegmentTree, 0, 3, 0) . Qui, low
non è lo stesso high
, otterremo un mid
. La calling line
indica quale ConstructTree
viene chiamato dopo questa dichiarazione. Indichiamo le chiamate ConstructTree
all'interno della procedura come 1 e 2 rispettivamente. La nostra tabella sarà simile a:
+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
| 0 | 3 | 0 | 1 | 1 |
+-----+------+----------+-----+--------------+
Quindi, quando chiamiamo ConstructTree-1
, passiamo: low = 0
, high = mid = 1
, position = 2*position+1 = 2*0+1 = 1
. Una cosa che puoi notare, ovvero 2*position+1
è il figlio sinistro di root , che è 1 . Dal momento che il low
non è uguale high
, otteniamo una mid
. La nostra tabella sarà simile a:
+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
| 0 | 3 | 0 | 1 | 1 |
+-----+------+----------+-----+--------------+
| 0 | 1 | 1 | 0 | 1 |
+-----+------+----------+-----+--------------+
Nella prossima chiamata ricorsiva, passiamo low = 0
, high = mid = 0
, position = 2*position+1 = 2*1+1=3
. Di nuovo il figlio sinistro dell'indice 1 è 3 . Qui, low
è high
, quindi impostiamo SegmentTree[position] = SegmentTree[3] = Item[low] = Item[0] = -1
. Il nostro array Segmentare sarà simile a:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+
| inf | inf | inf | -1 | inf | inf | inf |
+-----+-----+-----+-----+-----+-----+-----+
La nostra tabella di ricorsione sarà simile a:
+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
| 0 | 3 | 0 | 1 | 1 |
+-----+------+----------+-----+--------------+
| 0 | 1 | 1 | 0 | 1 |
+-----+------+----------+-----+--------------+
| 0 | 0 | 3 | | |
+-----+------+----------+-----+--------------+
Quindi puoi vedere, -1 ha la sua posizione corretta. Poiché questa chiamata ricorsiva è completa, torniamo alla riga precedente della nostra tabella di ricorsione. La tavola:
+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
| 0 | 3 | 0 | 1 | 1 |
+-----+------+----------+-----+--------------+
| 0 | 1 | 1 | 0 | 1 |
+-----+------+----------+-----+--------------+
Nella nostra procedura, eseguiamo la chiamata ConstructTree-2
. Questa volta, passiamo low = mid+1 = 1
, high = 1
, position = 2*position+2 = 2*1+2 = 4
. La nostra calling line
cambia in 2 . Noi abbiamo:
+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
| 0 | 3 | 0 | 1 | 1 |
+-----+------+----------+-----+--------------+
| 0 | 1 | 1 | 0 | 2 |
+-----+------+----------+-----+--------------+
Dato che low
è uguale a high
, impostiamo: SegmentTree[position] = SegmentTree[4] = Item[low] = Item[1] = 2
. Il nostro array SegmentTree :
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+
| inf | inf | inf | -1 | 2 | inf | inf |
+-----+-----+-----+-----+-----+-----+-----+
La nostra tabella di ricorsione:
+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
| 0 | 3 | 0 | 1 | 1 |
+-----+------+----------+-----+--------------+
| 0 | 1 | 1 | 0 | 2 |
+-----+------+----------+-----+--------------+
| 1 | 1 | 4 | | |
+-----+------+----------+-----+--------------+
Di nuovo puoi vedere, 2 ha la sua posizione corretta. Dopo questa chiamata ricorsiva, torniamo alla riga precedente della nostra tabella di ricorsione. Noi abbiamo:
+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
| 0 | 3 | 0 | 1 | 1 |
+-----+------+----------+-----+--------------+
| 0 | 1 | 1 | 0 | 2 |
+-----+------+----------+-----+--------------+
Eseguiamo l'ultima riga della nostra procedura, SegmentTree[position] = SegmentTree[1] = min(SegmentTree[2*position+1], SegmentTree[2*position+2]) = min(SegmentTree[3], SegmentTree[4]) = min(-1,2) = -1
. Il nostro array SegmentTree :
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+
| inf | -1 | inf | -1 | 2 | inf | inf |
+-----+-----+-----+-----+-----+-----+-----+
Poiché questa chiamata di ricorsione è completa, torniamo alla riga precedente della nostra tabella di ricorsione e chiamiamo ConstructTree-2
:
+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
| 0 | 3 | 0 | 1 | 2 |
+-----+------+----------+-----+--------------+
Possiamo vedere che la parte sinistra del nostro albero del segmento è completa. Se continuiamo in questo modo, dopo aver completato l'intera procedura, otterremo finalmente un array SegmentTree completato, che sarà simile a:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+
| -1 | -1 | 0 | -1 | 2 | 4 | 0 |
+-----+-----+-----+-----+-----+-----+-----+
La complessità temporale e spaziale della costruzione di questo array Segmentazione è: O(n)
, dove n indica il numero di elementi nell'array Articolo . Il nostro array SegmentTree può essere utilizzato per eseguire Range Minimum Query (RMQ) . Per costruire una matrice per eseguire la query massima intervallo , dobbiamo sostituire la linea:
SegmentTree[position] := min(SegmentTree[2*position+1], SegmentTree[2*position+2])
con:
SegmentTree[position] := max(SegmentTree[2*position+1], SegmentTree[2*position+2])
Esecuzione di una query minima di intervallo
La procedura per eseguire un RMQ è già mostrata nell'introduzione. Lo pseudo-codice per il controllo della query minima intervallo sarà:
Procedure RangeMinimumQuery(SegmentTree, qLow, qHigh, low, high, position):
if qLow <= low and qHigh >= high //Total Overlap
Return SegmentTree[position]
else if qLow > high || qHigh < low //No Overlap
Return infinity
else //Partial Overlap
mid := (low+high)/2
Return min(RangeMinimumQuery(SegmentTree, qLow, qHigh, low, mid, 2*position+1),
RangeMinimumQuery(SegmentTree, qLow, qHigh, mid+1, high, 2*position+2))
end if
Qui, qLow = The lower range of our query
, qHigh = The upper range of our query
. low = starting index of Item array
, high = Finishing index of Item array
, position = root = 0
. Ora proviamo a capire la procedura usando l'esempio che abbiamo creato prima:
Il nostro array SegmentTree :
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+
| -1 | -1 | 0 | -1 | 2 | 4 | 0 |
+-----+-----+-----+-----+-----+-----+-----+
Vogliamo trovare il minimo nel range [1,3] .
Poiché si tratta di una procedura ricorsiva, vedremo il funzionamento di RangeMinimumQuery
utilizzando una tabella di ricorsività che tiene traccia di qLow
, qHigh
, low
, high
, position
, mid
e calling line
. Inizialmente chiamiamo RangeMinimumQuery (SegmentTree, 1, 3, 0, 3, 0. Qui, le prime due condizioni non sono soddisfatte (sovrapposizione parziale). RangeMinimumQuery
un valore mid
La calling line
indica quale RangeMinimumQuery
viene chiamato dopo questo dichiarazione. Indichiamo le chiamate RangeMinimumQuery
all'interno della procedura come 1 e 2. La nostra tabella sarà simile a:
+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 0 | 3 | 0 | 1 | 1 |
+------+-------+-----+------+----------+-----+--------------+
Quindi, quando chiamiamo RangeMinimumQuery-1
, passiamo: low = 0
, high = mid = 1
, position = 2*position+1 = 1
. Una cosa che puoi notare, ovvero 2*position+1
è il figlio sinistro di un nodo . Ciò significa che stiamo controllando il figlio sinistro di root . Poiché [1,3] si sovrappone parzialmente [0,1] , le prime due condizioni non sono soddisfatte, otteniamo una mid
. La nostra tabella:
+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 0 | 3 | 0 | 1 | 1 |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 0 | 1 | 1 | 0 | 1 |
+------+-------+-----+------+----------+-----+--------------+
Nella prossima chiamata ricorsiva, passiamo low = 0
, high = mid = 0
, position = 2*position+1 = 3
. Raggiungiamo la foglia più a sinistra del nostro albero. Poiché [1,3] non si sovrappone a [0,0] , restituiamo l' infinity
alla nostra funzione di chiamata. Tabella ricorsiva:
+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 0 | 3 | 0 | 1 | 1 |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 0 | 1 | 1 | 0 | 1 |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 0 | 0 | 3 | | |
+------+-------+-----+------+----------+-----+--------------+
Poiché questa chiamata ricorsiva è completa, torniamo alla riga precedente della nostra tabella di ricorsione. Noi abbiamo:
+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 0 | 3 | 0 | 1 | 1 |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 0 | 1 | 1 | 0 | 1 |
+------+-------+-----+------+----------+-----+--------------+
Nella nostra procedura, RangeMinimumQuery-2
chiamata RangeMinimumQuery-2
. Questa volta, passiamo low = mid+1 = 1
, high = 1
e position = 2*position+2 = 4
. La nostra calling line changes to **2**
. Noi abbiamo:
+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 0 | 3 | 0 | 1 | 1 |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 0 | 1 | 1 | 0 | 2 |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 1 | 1 | 4 | | |
+------+-------+-----+------+----------+-----+--------------+
Quindi stiamo andando al figlio giusto del nodo precedente. Questa volta c'è una sovrapposizione totale. Restituiamo il valore SegmentTree[position] = SegmentTree[4] = 2
.
+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 0 | 3 | 0 | 1 | 1 |
+------+-------+-----+------+----------+-----+--------------+
Tornando alla funzione chiamante, stiamo controllando quale sia il minimo dei due valori restituiti di due funzioni di chiamata. Ovviamente il minimo è 2 , restituiamo 2 alla funzione chiamante. La nostra tabella di ricorsione sembra:
+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 0 | 3 | 0 | 1 | 1 |
+------+-------+-----+------+----------+-----+--------------+
Abbiamo finito di esaminare la parte sinistra del nostro segmento di albero. Ora chiameremo RangeMinimumQuery-2
da qui. Passeremo low = mid+1 = 1+1 =2
, high = 3
e position = 2*position+2 = 2
. La nostra tabella:
+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 0 | 3 | 0 | 1 | 1 |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 2 | 3 | 2 | | |
+------+-------+-----+------+----------+-----+--------------+
C'è una sovrapposizione totale. Quindi restituiamo il valore: SegmentTree[position] = SegmentTree[2] = 0
. Ritorniamo alla ricorsione da dove sono stati chiamati questi due bambini e otteniamo il minimo di (4,0) , ovvero 0 e restituiamo il valore.
Dopo aver eseguito la procedura, otteniamo 0 , che è il minimo da index- 1 a index- 3 .
La complessità del runtime per questa procedura è O(logn)
dove n è il numero di elementi nell'array Items . Per eseguire una query massima intervallo, è necessario sostituire la linea:
Return min(RangeMinimumQuery(SegmentTree, qLow, qHigh, low, mid, 2*position+1),
RangeMinimumQuery(SegmentTree, qLow, qHigh, mid+1, high, 2*position+2))
con:
Return max(RangeMinimumQuery(SegmentTree, qLow, qHigh, low, mid, 2*position+1),
RangeMinimumQuery(SegmentTree, qLow, qHigh, mid+1, high, 2*position+2))
Propagazione pigra
Diciamo che hai già creato un albero del segmento. È necessario aggiornare i valori dell'array, questo non solo cambierà i nodi foglia dell'albero del segmento, ma anche il minimo / massimo in alcuni nodi. Diamo un'occhiata a questo con un esempio:
Questo è il nostro albero di segmento minimo di 8 elementi. Per darti un rapido promemoria, ciascun nodo rappresenta il valore minimo dell'intervallo menzionato accanto a loro. Diciamo che vogliamo incrementare il valore del primo elemento del nostro array di 3 . Come possiamo farlo? Seguiremo il modo in cui abbiamo condotto RMQ. Il processo sarebbe simile a:
- All'inizio attraversiamo la radice. [0,0] si sovrappone parzialmente a [0,7] , andiamo in entrambe le direzioni.
- Al sottostruttura di sinistra, [0,0] si sovrappone parzialmente a [0,3] , andiamo in entrambe le direzioni.
- Al sottostruttura di sinistra, [0,0] si sovrappone parzialmente a [0,1] , andiamo in entrambe le direzioni.
- Al sottoalbero sinistro, [0,0] si sovrappone completamente a [0,0] , e dal suo nodo foglia, aggiorniamo il nodo aumentandolo di 3 . E restituire il valore -1 + 3 = 2 .
- Al sottoalbero destro, [1,1] non si sovrappone a [0,0] , restituiamo il valore sul nodo ( 2 ).
Il minimo di questi due valori restituiti ( 2 , 2 ) è 2 , quindi aggiorniamo il valore del nodo corrente e lo restituiamo.
- Al sottostruttura di destra [2,3] non si sovrappone a [0,0] , restituiamo il valore del nodo. ( 1 ).
Poiché il minimo di questi due valori restituiti ( 2 , 1 ) è 1 , aggiorniamo il valore del nodo corrente e lo restituisce.
- Al sottostruttura di sinistra, [0,0] si sovrappone parzialmente a [0,1] , andiamo in entrambe le direzioni.
- Al sottoalbero destro [4,7] non si sovrappone a [0,0] , restituiamo il valore del nodo. ( 1 ).
- Al sottostruttura di sinistra, [0,0] si sovrappone parzialmente a [0,3] , andiamo in entrambe le direzioni.
- Infine, il valore del nodo root viene aggiornato poiché il minimo dei due valori restituiti (1,1) è 1 .
Possiamo vedere che l'aggiornamento di un singolo nodo richiede la complessità del tempo O(logn)
, dove n è il numero di nodi foglia. Quindi, se ci viene chiesto di aggiornare alcuni nodi da i a j , sarà necessaria la complessità temporale di O(nlogn)
. Questo diventa ingombrante per un grande valore di n . Cerchiamo di essere pigri cioè, funzionano solo quando necessario. Come? Quando è necessario aggiornare un intervallo, aggiorneremo un nodo e contrassegneremo il suo bambino che deve essere aggiornato e aggiornarlo quando necessario. Per questo abbiamo bisogno di un array pigro della stessa dimensione di un albero del segmento. Inizialmente tutti gli elementi dell'array pigro saranno 0 che rappresentano che non vi è alcun aggiornamento in sospeso. Se c'è un elemento diverso da zero in lazy [i] , allora questo elemento deve aggiornare il nodo i nell'albero del segmento prima di eseguire qualsiasi operazione di query. Come lo faremo? Diamo un'occhiata a un esempio:
Diciamo, per il nostro albero di esempio, vogliamo eseguire alcune query. Questi sono:
- incremento [0,3] per 3 .
- incremento [0,3] di 1 .
- incremento [0,0] di 2 .
incremento [0,3] per 3:
Iniziamo dal nodo radice. Inizialmente, controlliamo se questo valore è aggiornato. Per questo controlliamo il nostro array pigro che è 0 , il che significa che il valore è aggiornato. [0,3] si sovrappone parzialmente [0,7] . Quindi andiamo ad entrambe le direzioni.
- Nel sottoalbero di sinistra, non ci sono aggiornamenti in sospeso. [0,3] si sovrappone totalmente [0,3] . Quindi aggiorniamo il valore del nodo per 3 . Quindi il valore diventa -1 + 3 = 2 . Questa volta non andremo fino in fondo. Invece di andare giù, aggiorniamo il bambino corrispondente nell'albero pigro del nostro nodo corrente e lo incrementiamo di 3 . Restituiamo anche il valore del nodo corrente.
- Nella sottostruttura di destra, non ci sono aggiornamenti in sospeso. [0,3] non si sovrappone [4,7] . Quindi restituiamo il valore del nodo corrente (1) .
Il minimo di due valori restituiti ( 2 , 1 ) è 1 . Aggiorniamo il nodo root su 1 .
Il nostro albero del segmento e l'albero pigro assomigliano a:
I valori diversi da zero nei nodi del nostro Lazy Tree rappresentano, ci sono aggiornamenti in sospeso in quei nodi e sotto. Li aggiorneremo se necessario. Se ci viene chiesto, qual è il minimo nell'intervallo [0,3] , verremo nella sottostruttura di sinistra del nodo radice e poiché non ci sono aggiornamenti in sospeso, restituiremo 2 , che è corretto. Quindi questo processo non influisce sulla correttezza dell'algoritmo dell'albero dei segmenti.
incremento [0,3] per 1:
- Iniziamo dal nodo radice. Non ci sono aggiornamenti in sospeso. [0,3] si sovrappone parzialmente [0,7] . Quindi andiamo in entrambe le direzioni.
- Nel sottoalbero di sinistra, non ci sono aggiornamenti in attesa. [0,3] si sovrappone completamente [0,3] . Aggiorniamo il nodo corrente: 2 + 1 = 3 . Poiché questo è un nodo interno, aggiorniamo i suoi figli nella Lazy Tree per essere incrementati di 1 . Restituiremo anche il valore del nodo corrente ( 3 ).
- Nella sottostruttura di destra, non ci sono aggiornamenti in sospeso. [0,3] non si sovrappone [4,7] . Restituiamo il valore del nodo corrente ( 1 ).
- Aggiorniamo il nodo radice prendendo il minimo di due valori restituiti ( 3 , 1 ).
Il nostro albero del segmento e l'albero pigro avranno il seguente aspetto:
Come puoi vedere, stiamo accumulando gli aggiornamenti su Lazy Tree ma non spingendoli verso il basso. Questo è ciò che significa propagazione pigra. Se non lo avessimo usato, dovevamo spingere i valori verso le foglie, il che ci costerebbe una maggiore complessità temporale non necessaria.
incremento [0,0] per 2:
- Iniziamo dal nodo radice. Poiché root è aggiornato e [0,0] si sovrappone parzialmente [0,7] , andiamo in entrambe le direzioni.
- Al sottoalbero sinistro, il nodo corrente è aggiornato e [0,0] si sovrappone parzialmente [0,3] , andiamo in entrambe le direzioni.
- Nel sottoalbero sinistro, il nodo corrente in Lazy Tree ha un valore diverso da zero. Quindi c'è un aggiornamento che non è stato ancora propagato a questo nodo. Stiamo per prima aggiornare questo nodo nella nostra struttura dei segmenti. Quindi questo diventa -1 + 4 = 3 . Quindi propagheremo questo 4 ai suoi figli nel Lazy Tree. Dato che abbiamo già aggiornato il nodo corrente, cambieremo il valore del nodo corrente in Lazy Tree a 0 . Quindi [0,0] si sovrappone parzialmente [0,1] , quindi andiamo in entrambe le direzioni.
- Al nodo sinistro, il valore deve essere aggiornato poiché esiste un valore diverso da zero nel nodo corrente di Lazy Tree. Quindi aggiorniamo il valore a -1 + 4 = 3 . Ora, poiché [0,0] si sovrappone totalmente [0,0] , aggiorniamo il valore del nodo corrente su 3 + 2 = 5 . Questo è un nodo foglia, quindi non è più necessario propagare il valore. Aggiorniamo il nodo corrispondente su Lazy Tree su 0 poiché tutti i valori sono stati propagati fino a questo nodo. Restituiamo il valore del nodo corrente ( 5 ).
- Al nodo giusto, il valore deve essere aggiornato. Quindi il valore diventa: 4 + 2 = 6 . Poiché [0,0] non si sovrappone a [1,1] , restituiamo il valore del nodo corrente ( 6 ). Aggiorniamo anche il valore in Lazy Tree su 0 . Non è necessaria alcuna propagazione poiché questo è un nodo foglia.
Aggiorniamo il nodo corrente utilizzando il minimo di due valori restituiti ( 5 , 6 ). Restituiamo il valore del nodo corrente ( 5 ).
- Nella sottostruttura di destra, c'è un aggiornamento in sospeso. Aggiorniamo il valore del nodo su 1 + 4 = 5 . Poiché questo non è un nodo foglia, propagiamo il valore ai suoi figli nella nostra Lazy Tree e aggiorniamo il nodo corrente su 0 . Poiché [0,0] non si sovrappone a [2,3] , restituiamo il valore del nostro nodo corrente ( 5 ).
Aggiorniamo il nodo corrente usando il minimo dei valori restituiti ( 5 , 5 ) e restituiamo il valore ( 5 ).
- Nel sottoalbero sinistro, il nodo corrente in Lazy Tree ha un valore diverso da zero. Quindi c'è un aggiornamento che non è stato ancora propagato a questo nodo. Stiamo per prima aggiornare questo nodo nella nostra struttura dei segmenti. Quindi questo diventa -1 + 4 = 3 . Quindi propagheremo questo 4 ai suoi figli nel Lazy Tree. Dato che abbiamo già aggiornato il nodo corrente, cambieremo il valore del nodo corrente in Lazy Tree a 0 . Quindi [0,0] si sovrappone parzialmente [0,1] , quindi andiamo in entrambe le direzioni.
- Nella sottostruttura di destra, non ci sono aggiornamenti in sospeso e poiché [0,0] non si sovrappone a [4,7] , restituiamo il valore del nodo corrente ( 1 ).
- Al sottoalbero sinistro, il nodo corrente è aggiornato e [0,0] si sovrappone parzialmente [0,3] , andiamo in entrambe le direzioni.
- Aggiorniamo il nodo root usando il minimo dei due valori restituiti ( 5 , 1 ).
Il nostro albero del segmento e l'albero pigro avranno il seguente aspetto:
Possiamo notare che, il valore a [0,0] , quando necessario, ha ottenuto tutto l'incremento.
Ora se ti viene chiesto di trovare il minimo nell'intervallo [3,5] , se hai capito fino a questo punto, puoi facilmente capire come andrebbe la query e il valore restituito sarà 1 . Il nostro segmento Tree and Lazy Tree sarebbe simile a:
Abbiamo semplicemente seguito lo stesso processo che abbiamo seguito nella ricerca di RMQ con ulteriori limitazioni nel controllo di Lazy Tree per gli aggiornamenti in sospeso.
Un'altra cosa che possiamo fare è invece di restituire i valori da ciascun nodo, poiché sappiamo quale sarà il nodo figlio del nostro nodo corrente, possiamo semplicemente controllarli per trovare il minimo di questi due.
Lo pseudo-codice per l'aggiornamento in Lazy Propagation potrebbe essere:
Procedure UpdateSegmentTreeLazy(segmentTree, LazyTree, startRange,
endRange, delta, low, high, position):
if low > high //out of bounds
Return
end if
if LazyTree[position] is not equal to 0 //update needed
segmentTree[position] := segmentTree[position] + LazyTree[position]
if low is not equal to high //non-leaf node
LazyTree[2 * position + 1] := LazyTree[2 * position + 1] + delta
LazyTree[2 * position + 2] := LazyTree[2 * position + 2] + delta
end if
LazyTree[position] := 0
end if
if startRange > low or endRange < high //doesn't overlap
Return
end if
if startRange <= low && endRange >= high //total overlap
segmentTree[position] := segmentTree[position] + delta
if low is not equal to high
LazyTree[2 * position + 1] := LazyTree[2 * position + 1] + delta
LazyTree[2 * position + 2] := LazyTree[2 * position + 2] + delta
end if
Return
end if
//if we reach this portion, this means there's a partial overlap
mid := (low + high) / 2
UpdateSegmentTreeLazy(segmentTree, LazyTree, startRange,
endRange, delta, low, mid, 2 * position + 1)
UpdateSegmentTreeLazy(segmentTree, LazyTree, startRange,
endRange, delta, mid + 1, high, 2 * position + 2)
segmentTree[position] := min(segmentTree[2 * position + 1],
segmentTree[2 * position + 2])
E lo pseudo-codice per RMQ in Lazy Propagation sarà:
Procedure RangeMinimumQueryLazy(segmentTree, LazyTree, qLow, qHigh, low, high, position):
if low > high
Return infinity
end if
if LazyTree[position] is not equal to 0 //update needed
segmentTree[position] := segmentTree[position] + LazyTree[position]
if low is not equal to high
segmentTree[position] := segmentTree[position] + LazyTree[position]
if low is not equal to high //non-leaf node
LazyTree[2 * position + 1] := LazyTree[2 * position + 1] + LazyTree[position]
LazyTree[2 * position + 2] := LazyTree[2 * position + 2] + LazyTree[position]
end if
LazyTree[position] := 0
end if
if qLow > high and qHigh < low //no overlap
Return infinity
end if
if qLow <= low and qHigh >= high //total overlap
Return segmentTree[position]
end if
//if we reach this portion, this means there's a partial overlap
mid := (low + high) / 2
Return min(RangeMinimumQueryLazy(segmentTree, LazyTree, qLow, qHigh,
low, mid, 2 * position + 1),
RangeMinimumQueryLazy(segmentTree, LazyTree, qLow, qHigh,
mid + 1, high, 2 * position + 1)