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à:

Matrice segmentata

Ora se sostituiamo i nodi non foglia con il valore minimo delle loro foglie, otteniamo:

Valori minimi sostituiti

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:

Albero del segmento

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.
  • 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:

Albero del segmento

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: Nuovo esempio (-1, 2, 4, 0)

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:

Esempio di albero del segmento

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:

Esempio di albero del segmento

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 sottoalbero destro [4,7] non si sovrappone a [0,0] , restituiamo il valore del nodo. ( 1 ).
  • 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:

Albero del segmento e albero pigro

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:

Albero del segmento e albero pigro aggiornati

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

Aggiornato l'albero dei segmenti e l'albero pigro

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:

Albero pigro e albero del segmento dopo la query

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)


Modified text is an extract of the original Stack Overflow Documentation
Autorizzato sotto CC BY-SA 3.0
Non affiliato con Stack Overflow