data-structures => Drzewo segmentów

Wprowadzenie do drzewa segmentów

Załóżmy, że mamy tablicę:

+-------+-----+-----+-----+-----+-----+-----+
| Index |  0  |  1  |  2  |  3  |  4  |  5  |
+-------+-----+-----+-----+-----+-----+-----+
| Value |  -1 |  3  |  4  |  0  |  2  |  1  |
+-------+-----+-----+-----+-----+-----+-----+

Chcemy wykonać zapytanie dotyczące tej tablicy. Na przykład:

Jakie jest minimum od indeksu- 2 do indeksu- 4 ? -> 0
Jaka jest maksymalna wartość od indeksu 0 do indeksu 3 ? -> 4
Co to jest suma od indeksu 1 do indeksu 5 ? -> 10

Jak się tego dowiemy?

Brutalna siła:
Możemy przejść przez tablicę od indeksu początkowego do indeksu końcowego i odpowiedzieć na nasze zapytanie. W tym podejściu każde zapytanie zajmuje czas O(n) gdzie n jest różnicą między indeksem początkowym a indeksem końcowym. Ale co jeśli są miliony liczb i miliony zapytań? Dla m zapytań zajęłoby to O(mn) czas. Tak więc dla 10⁵ wartości w naszej tablicy, jeśli przeprowadzimy zapytania 10,, w najgorszym przypadku będziemy musieli przejść 10¹⁰ elementów.

Programowanie dynamiczne:
Możemy stworzyć macierz 6X6 do przechowywania wartości dla różnych zakresów. W przypadku zapytania minimalnego zakresu (RMQ) nasza tablica wyglądałaby następująco:

              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  |
     +-----+-----+-----+-----+-----+-----+-----+

Gdy będziemy mieć tę kompilację macierzy, wystarczy odpowiedzieć na wszystkie RMQ. Tutaj macierz [i] [j] przechowuje minimalną wartość od indeksu- i do indeksu- j . Na przykład: minimum od indeksu- 2 do indeksu- 4 to Matryca [2] [4] = 0 . Ta macierz odpowiada na zapytanie w czasie O(1) , ale zbudowanie tej macierzy zajmuje O (n²) , a przestrzeń O(n²) do jej przechowywania. Więc jeśli n jest naprawdę dużą liczbą, nie skaluje się to zbyt dobrze.

Drzewo segmentu:
Drzewo segmentów to struktura danych drzewa do przechowywania przedziałów lub segmentów. Umożliwia sprawdzenie, który z zapisanych segmentów zawiera dany punkt. To zajmuje O(n) czasu, aby zbudować drzewo segmencie zajmuje O(n) miejsca, aby utrzymać go i odpowiada na zapytanie w O(logn) czasu.

Drzewo segmentu jest drzewem binarnym, a elementami danej tablicy będą liście tego drzewa. Utworzymy drzewo segmentów, dzieląc tablicę na pół, aż dojdziemy do jednego elementu. Nasz dział zapewniłby nam:

Teraz, jeśli zastąpimy węzły inne niż liście minimalną wartością ich liści, otrzymamy:

To jest nasze drzewo segmentów. Możemy zauważyć, że węzeł główny zawiera minimalną wartość całej tablicy (zakres [0,5]), jego lewe dziecko zawiera minimalną wartość naszej lewej tablicy (zakres [0,2]), prawe dziecko zawiera minimum wartość naszej prawej tablicy (zakres [3,5]) i tak dalej. Węzły liścia zawierają minimalną wartość każdego pojedynczego punktu. Otrzymujemy:

Teraz zróbmy zapytanie o zakres na tym drzewie. Aby wykonać zapytanie o zakres, musimy sprawdzić trzy warunki:

Częściowe zachodzenie na siebie: Sprawdzamy oba liście.
Całkowite nakładanie się: zwracamy wartość przechowywaną w węźle.
Bez nakładania się: zwracamy bardzo dużą wartość lub nieskończoność.

Powiedzmy, że chcemy sprawdzić zakres [2,4] , co oznacza, że chcemy znaleźć minimum od indeksu - 2 do 4 . Zaczniemy od katalogu głównego i sprawdzimy, czy zakres w naszych węzłach pokrywa się z naszym zakresem zapytań, czy nie. Tutaj,

[2,4] nie pokrywa się całkowicie [0,5] . Sprawdzimy więc oba kierunki.
- W lewym poddrzewie [2,4] częściowo zachodzi na siebie [0,2] . Sprawdzimy oba kierunki.
  - W lewym poddrzewie [2,4] nie pokrywa się [0,1] , więc nie przyczyni się to do naszej odpowiedzi. Zwracamy nieskończoność .
  - W prawym poddrzewie [2,4] całkowicie zachodzi na siebie [2,2] . Zwracamy 4 .
    Minimalna z tych dwóch zwracanych wartości (4, nieskończoność) wynosi 4 . Otrzymujemy 4 z tej części.
- W prawym poddrzewie [2,4] częściowo zachodzi na siebie. Sprawdzimy więc oba kierunki.
  - W lewym poddrzewie [2,4] całkowicie zachodzi na siebie [3,4] . Zwracamy 0 .
  - W prawym poddrzewie [2,4] nie pokrywa się [5,5] . Zwracamy nieskończoność .
    Minimalna z tych dwóch zwracanych wartości (0, nieskończoność) wynosi 0 . Otrzymujemy 0 z tej części.
Minimalna liczba zwracanych wartości (4,0) wynosi 0 . To jest nasze pożądane minimum w zakresie [2,4] .

Teraz możemy sprawdzić, czy bez względu na to, jakie jest nasze zapytanie, znalezienie żądanej wartości z tego drzewa segmentów wymagałoby maksymalnie 4 kroków.

Posługiwać się:

Zasięg Minimalne zapytanie
Najniższy wspólny przodek
Leniwe propagowanie
Dynamiczna suma poddrzewa
Zaniedbanie i min
Podwójne pola
Znalezienie k-tego najmniejszego elementu
Znajdowanie liczby nieuporządkowanych par

Implementacja drzewa segmentów za pomocą tablicy

Powiedzmy, że mamy tablicę: Item = {-1, 0, 3, 6} . Chcemy zbudować tablicę SegmentTree, aby znaleźć minimalną wartość w danym zakresie. Nasze drzewo segmentów będzie wyglądać następująco:

Liczby poniżej węzłów pokazują indeksy poszczególnych wartości, które będziemy przechowywać w naszej tablicy SegmentTree . Widzimy, że do przechowywania 4 elementów potrzebowaliśmy tablicy o rozmiarze 7. Ta wartość jest określana przez:

Procedure DetermineArraySize(Item):
multiplier := 1
n := Item.size
while multiplier < n
    multiplier := multiplier * 2
end while
size := (2 * multiplier) - 1
Return size

Gdybyśmy mieli tablicę o długości 5, rozmiar naszej tablicy SegmentTree wynosiłby: ( 8 * 2 ) - 1 = 15 . Teraz, aby określić pozycję lewego i prawego potomka węzła, jeśli węzeł znajduje się w indeksie i , to jego pozycja:

Lewe dziecko jest oznaczone przez: (2 * i) + 1 .
Prawe dziecko jest oznaczone przez: (2 * i) + 2 .

Indeks rodzica dowolnego węzła w indeksie i można określić przez: (i - 1) / 2 .

Tablica SegmentTree reprezentująca nasz przykład wyglądałaby następująco:

   0     1     2     3     4     5     6
+-----+-----+-----+-----+-----+-----+-----+
|  -1 |  -1 |  3  |  -1 |  0  |  3  |  6  |
+-----+-----+-----+-----+-----+-----+-----+

Spójrzmy na pseudo-kod, aby skonstruować tę tablicę:

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

Najpierw pobieramy wartości i inicjujemy tablicę SegmentTree z infinity używając długości tablicy elementu jako jej rozmiaru. Procedurę nazywamy za pomocą:

low = Początkowy indeks tablicy przedmiotów .
high = indeks końcowy tablicy przedmiotów .
pozycja = 0, wskazuje katalog główny naszego drzewa segmentów.

Teraz spróbujmy zrozumieć procedurę na przykładzie:

Rozmiar naszej tablicy przedmiotów wynosi 4 . Tworzymy tablicę o długości (4 * 2) - 1 = 7 i inicjalizujemy je infinity . Możesz użyć do tego bardzo dużej wartości. Nasza tablica wyglądałaby następująco:

   0     1     2     3     4     5     6
+-----+-----+-----+-----+-----+-----+-----+
| inf | inf | inf | inf | inf | inf | inf |
+-----+-----+-----+-----+-----+-----+-----+

Ponieważ jest to procedura rekurencyjna, zobaczymy działanie ConstructTree przy użyciu tabeli rekurencji, która śledzi calling line low , high , position , mid i calling line przy każdym połączeniu. Najpierw wywołujemy ConstructTree (Item, SegmentTree, 0, 3, 0) . Tutaj low nie jest taki sam jak high , otrzymamy mid . Linia calling line wskazuje, który ConstructTree jest wywoływany po tej instrukcji. Oznaczamy wywołania ConstructTree wewnątrz procedury odpowiednio jako 1 i 2 . Nasz stół będzie wyglądał następująco:

+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
|  0  |   3  |     0    |  1  |       1      |
+-----+------+----------+-----+--------------+

Kiedy wywołujemy ConstructTree-1 , mijamy: low = 0 , high = mid = 1 , position = 2*position+1 = 2*0+1 = 1 . Jedną z rzeczy, które można zauważyć, jest 2*position+1 to lewe dziecko root , czyli 1 . Ponieważ low nie jest równy high , otrzymujemy mid . Nasz stół będzie wyglądał następująco:

+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
|  0  |   3  |     0    |  1  |       1      |
+-----+------+----------+-----+--------------+
|  0  |   1  |     1    |  0  |       1      |
+-----+------+----------+-----+--------------+

W kolejnym wywołaniu rekurencyjnym przekazujemy low = 0 , high = mid = 0 , position = 2*position+1 = 2*1+1=3 . Ponownie lewe dziecko o indeksie 1 ma 3 . Tutaj low jest e high , więc ustawiamy SegmentTree[position] = SegmentTree[3] = Item[low] = Item[0] = -1 . Nasza tablica SegmentTree będzie wyglądać następująco:

   0     1     2     3     4     5     6
+-----+-----+-----+-----+-----+-----+-----+
| inf | inf | inf |  -1 | inf | inf | inf |
+-----+-----+-----+-----+-----+-----+-----+

Nasza tabela rekurencji będzie wyglądać następująco:

+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
|  0  |   3  |     0    |  1  |       1      |
+-----+------+----------+-----+--------------+
|  0  |   1  |     1    |  0  |       1      |
+-----+------+----------+-----+--------------+
|  0  |   0  |     3    |     |              |
+-----+------+----------+-----+--------------+

Jak widać, -1 ma prawidłową pozycję. Ponieważ to wywołanie rekurencyjne zostało zakończone, wracamy do poprzedniego wiersza naszej tabeli rekurencji. Stół:

+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
|  0  |   3  |     0    |  1  |       1      |
+-----+------+----------+-----+--------------+
|  0  |   1  |     1    |  0  |       1      |
+-----+------+----------+-----+--------------+

W naszej procedurze wykonujemy wywołanie ConstructTree-2 . Tym razem mijamy low = mid+1 = 1 , high = 1 , position = 2*position+2 = 2*1+2 = 4 . Nasza calling line zmienia się na 2 . Otrzymujemy:

+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
|  0  |   3  |     0    |  1  |       1      |
+-----+------+----------+-----+--------------+
|  0  |   1  |     1    |  0  |       2      |
+-----+------+----------+-----+--------------+

Ponieważ low jest równa high , ustawiamy: SegmentTree[position] = SegmentTree[4] = Item[low] = Item[1] = 2 . Nasza tablica SegmentTree :

   0     1     2     3     4     5     6
+-----+-----+-----+-----+-----+-----+-----+
| inf | inf | inf |  -1 |  2  | inf | inf |
+-----+-----+-----+-----+-----+-----+-----+

Nasz stół rekurencyjny:

+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
|  0  |   3  |     0    |  1  |       1      |
+-----+------+----------+-----+--------------+
|  0  |   1  |     1    |  0  |       2      |
+-----+------+----------+-----+--------------+
|  1  |   1  |     4    |     |              |
+-----+------+----------+-----+--------------+

Ponownie widać, że 2 ma prawidłową pozycję. Po tym wywołaniu rekurencyjnym wracamy do poprzedniego wiersza naszej tabeli rekurencji. Otrzymujemy:

+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
|  0  |   3  |     0    |  1  |       1      |
+-----+------+----------+-----+--------------+
|  0  |   1  |     1    |  0  |       2      |
+-----+------+----------+-----+--------------+

Wykonujemy ostatni wiersz naszej procedury, SegmentTree[position] = SegmentTree[1] = min(SegmentTree[2*position+1], SegmentTree[2*position+2]) = min(SegmentTree[3], SegmentTree[4]) = min(-1,2) = -1 . Nasza tablica SegmentTree :

   0     1     2     3     4     5     6
+-----+-----+-----+-----+-----+-----+-----+
| inf |  -1 | inf |  -1 |  2  | inf | inf |
+-----+-----+-----+-----+-----+-----+-----+

Ponieważ to wywołanie rekurencyjne jest zakończone, wracamy do poprzedniego wiersza naszej tabeli rekurencji i wywołujemy ConstructTree-2 :

+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
|  0  |   3  |     0    |  1  |       2      |
+-----+------+----------+-----+--------------+

Widzimy, że lewa część naszego drzewa segmentów jest kompletna. Jeśli będziemy kontynuować w ten sposób, po zakończeniu całej procedury otrzymamy w końcu kompletną tablicę SegmentTree , która będzie wyglądać następująco:

   0     1     2     3     4     5     6
+-----+-----+-----+-----+-----+-----+-----+
|  -1 |  -1 |  0  |  -1 |  2  |  4  |  0  |
+-----+-----+-----+-----+-----+-----+-----+

Czas i przestrzeń złożoność budowy tej tablicy SegmentTree jest: O(n) , gdzie n oznacza liczbę elementów tablicy elementu. Nasza skonstruowana tablica SegmentTree może być używana do wykonywania zapytania minimalnego zakresu (RMQ) . Aby zbudować tablicę do wykonywania zapytania o maksymalne zakresy , musimy zastąpić wiersz:

SegmentTree[position] := min(SegmentTree[2*position+1], SegmentTree[2*position+2])

SegmentTree[position] := max(SegmentTree[2*position+1], SegmentTree[2*position+2])

Wykonywanie zapytania minimalnego zakresu

Procedura wykonania RMQ jest już pokazana we wstępie. Pseudo-kod do sprawdzania zapytania minimalnego zakresu będzie:

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

Tutaj 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 . Teraz spróbujmy zrozumieć procedurę na przykładzie, który stworzyliśmy wcześniej:

Nasza tablica SegmentTree :

   0     1     2     3     4     5     6
+-----+-----+-----+-----+-----+-----+-----+
|  -1 |  -1 |  0  |  -1 |  2  |  4  |  0  |
+-----+-----+-----+-----+-----+-----+-----+

Chcemy znaleźć minimum w zakresie [1,3] .
Ponieważ jest to procedura rekurencyjna, zobaczymy działanie RangeMinimumQuery za pomocą tabeli rekurencji, która śledzi qLow , qHigh , low , high , position , mid i calling line . Najpierw wywołujemy RangeMinimumQuery (SegmentTree, 1, 3, 0, 3, 0. Tutaj pierwsze dwa warunki nie są spełnione (częściowe nakładanie się). Dostaniemy mid . Linia calling line wskazuje, który RangeMinimumQuery jest następnie wywoływany instrukcja RangeMinimumQuery wywołania RangeMinimumQuery wewnątrz procedury odpowiednio jako 1 i 2. Nasza tabela będzie wyglądać następująco:

+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
|   1  |   3   |  0  |   3  |     0    |  1  |       1      |
+------+-------+-----+------+----------+-----+--------------+

Kiedy wywołujemy RangeMinimumQuery-1 , mijamy: low = 0 , high = mid = 1 , position = 2*position+1 = 1 . Jedną z rzeczy, które można zauważyć, jest 2*position+1 to lewe dziecko węzła . Oznacza to, że sprawdzamy lewe dziecko roota . Ponieważ [1,3] częściowo pokrywa się z [0,1] , pierwsze dwa warunki nie są spełnione, otrzymujemy mid . Nasz stół:

+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
|   1  |   3   |  0  |   3  |     0    |  1  |       1      |
+------+-------+-----+------+----------+-----+--------------+
|   1  |   3   |  0  |   1  |     1    |  0  |       1      |
+------+-------+-----+------+----------+-----+--------------+

W kolejnym wywołaniu rekurencyjnym przekazujemy low = 0 , high = mid = 0 , position = 2*position+1 = 3 . Docieramy do lewego liścia naszego drzewa. Ponieważ [1,3] nie pokrywa się z [0,0] , przywracamy infinity do naszej funkcji wywoływania. Tabela rekurencji:

+------+-------+-----+------+----------+-----+--------------+
| 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    |     |              |
+------+-------+-----+------+----------+-----+--------------+

Ponieważ to wywołanie rekurencyjne zostało zakończone, wracamy do poprzedniego wiersza naszej tabeli rekurencji. Otrzymujemy:

+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
|   1  |   3   |  0  |   3  |     0    |  1  |       1      |
+------+-------+-----+------+----------+-----+--------------+
|   1  |   3   |  0  |   1  |     1    |  0  |       1      |
+------+-------+-----+------+----------+-----+--------------+

W naszej procedurze wykonujemy RangeMinimumQuery-2 . Tym razem mijamy low = mid+1 = 1 , high = 1 i position = 2*position+2 = 4 . Nasza calling line changes to **2** . Otrzymujemy:

+------+-------+-----+------+----------+-----+--------------+
| 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    |     |              |
+------+-------+-----+------+----------+-----+--------------+

Idziemy więc do właściwego potomka poprzedniego węzła. Tym razem zachodzi całkowite nakładanie się. Zwracamy wartość SegmentTree[position] = SegmentTree[4] = 2 .

+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
|   1  |   3   |  0  |   3  |     0    |  1  |       1      |
+------+-------+-----+------+----------+-----+--------------+

Wracając do funkcji wywołującej, sprawdzamy, co jest minimum z dwóch zwracanych wartości dwóch funkcji wywoływania. Oczywiście minimum to 2 , zwracamy 2 do funkcji wywoływania. Nasza tabela rekurencji wygląda następująco:

+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
|   1  |   3   |  0  |   3  |     0    |  1  |       1      |
+------+-------+-----+------+----------+-----+--------------+

Skończyliśmy patrzeć na lewą część naszego drzewa segmentów. Teraz nazwiemy RangeMinimumQuery-2 stąd. Przekażemy low = mid+1 = 1+1 =2 , high = 3 i position = 2*position+2 = 2 . Nasz stół:

+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
|   1  |   3   |  0  |   3  |     0    |  1  |       1      |
+------+-------+-----+------+----------+-----+--------------+
|   1  |   3   |  2  |   3  |     2    |     |              |
+------+-------+-----+------+----------+-----+--------------+

Całkowite nakładanie się. SegmentTree[position] = SegmentTree[2] = 0 więc wartość: SegmentTree[position] = SegmentTree[2] = 0 . Wracamy do rekurencji, z której wezwano te dwoje dzieci, i otrzymujemy minimum (4,0) , czyli 0 i zwracamy wartość.

Po wykonaniu procedury otrzymujemy 0 , czyli minimum od indeksu- 1 do indeksu- 3 .

Złożoność środowiska wykonawczego dla tej procedury wynosi O(logn) gdzie n jest liczbą elementów w tablicy Items . Aby wykonać zapytanie o maksymalne zakresy, musimy zastąpić wiersz:

Return min(RangeMinimumQuery(SegmentTree, qLow, qHigh, low, mid, 2*position+1),
               RangeMinimumQuery(SegmentTree, qLow, qHigh, mid+1, high, 2*position+2))

Return max(RangeMinimumQuery(SegmentTree, qLow, qHigh, low, mid, 2*position+1),
               RangeMinimumQuery(SegmentTree, qLow, qHigh, mid+1, high, 2*position+2))

Leniwe propagowanie

Powiedzmy, że utworzyłeś już drzewo segmentów. Musisz zaktualizować wartości tablicy, spowoduje to nie tylko zmianę węzłów liści twojego drzewa segmentów, ale także minimalne / maksymalne w niektórych węzłach. Spójrzmy na to na przykładzie:

To jest nasze minimalne drzewo segmentowe składające się z 8 elementów. Aby szybko przypomnieć, każdy węzeł reprezentuje minimalną wartość wspomnianego obok zakresu. Powiedzmy, że chcemy zwiększyć wartość pierwszego elementu naszej tablicy o 3 . Jak możemy to zrobić? Postępujemy zgodnie ze sposobem, w jaki przeprowadziliśmy RMQ. Proces wyglądałby następująco:

Na początku przemierzamy korzeń. [0,0] częściowo pokrywa się z [0,7] , idziemy w obu kierunkach.
- W lewym poddrzewie [0,0] częściowo pokrywa się z [0,3] , idziemy w obu kierunkach.
  - W lewym poddrzewie [0,0] częściowo pokrywa się z [0,1] , idziemy w obu kierunkach.
    - W lewym poddrzewie [0,0] całkowicie pokrywa się z [0,0] , a ponieważ jest to węzeł liścia, aktualizujemy węzeł, zwiększając jego wartość o 3 . I zwróć wartość -1 + 3 = 2 .
    - W prawym poddrzewie [1,1] nie pokrywa się z [0,0] , zwracamy wartość w węźle ( 2 ).
      Minimalna z tych dwóch zwracanych wartości ( 2 , 2 ) wynosi 2 , więc aktualizujemy wartość bieżącego węzła i zwracamy go.
  - W prawym poddrzewie [2,3] nie pokrywa się z [0,0] , zwracamy wartość węzła. ( 1 ).
    Ponieważ minimum tych dwóch zwracanych wartości ( 2 , 1 ) wynosi 1 , aktualizujemy wartość bieżącego węzła i zwracamy go.
- W prawym poddrzewie [4,7] nie pokrywa się z [0,0] , zwracamy wartość węzła. ( 1 ).
Na koniec wartość węzła głównego jest aktualizowana, ponieważ minimum dwie zwrócone wartości (1,1) wynoszą 1 .

Widzimy, że aktualizacja pojedynczego węzła wymaga złożoności czasowej O(logn) , gdzie n jest liczbą węzłów liści. Więc jeśli zostaniemy poproszeni o aktualizację niektórych węzłów od i do j , będziemy wymagać złożoności czasowej O(nlogn) . To staje się kłopotliwe dla dużej wartości n . Bądźmy leniwi, tzn. Pracujmy tylko w razie potrzeby. W jaki sposób? Kiedy musimy zaktualizować interwał, zaktualizujemy węzeł i oznaczymy jego dziecko, że musi zostać zaktualizowany, i zaktualizujemy go w razie potrzeby. W tym celu potrzebujemy tablicy leniwej o tym samym rozmiarze co drzewo segmentu. Początkowo wszystkie elementy leniwej tablicy będą miały wartość 0 , co oznacza brak oczekującej aktualizacji. Jeśli element leniwy [i] zawiera niezerowy element, wówczas element ten musi zaktualizować węzeł i w drzewie segmentu przed wykonaniem jakichkolwiek operacji zapytania. Jak to zrobimy? Spójrzmy na przykład:

Powiedzmy, że dla naszego przykładowego drzewa chcemy wykonać kilka zapytań. To są:

przyrost [0,3] o 3 .
przyrost [0,3] o 1 .
przyrost [0,0] o 2 .

inkrement [0,3] o 3:

Zaczynamy od węzła głównego. Najpierw sprawdzamy, czy ta wartość jest aktualna. W tym celu sprawdzamy naszą leniwą tablicę, która wynosi 0 , co oznacza, że wartość jest aktualna. [0,3] częściowo się pokrywa [0,7] . Idziemy więc w obie strony.
- W lewym poddrzewie nie ma oczekującej aktualizacji. [0,3] całkowicie pokrywa się [0,3] . Dlatego aktualizujemy wartość węzła o 3 . Tak więc wartość staje się -1 + 3 = 2 . Tym razem nie pójdziemy na całość. Zamiast schodzić w dół, aktualizujemy odpowiednie dziecko w leniwym drzewie naszego obecnego węzła i zwiększamy je o 3 . Zwracamy również wartość bieżącego węzła.
- W prawym poddrzewie nie ma oczekującej aktualizacji. [0,3] nie pokrywa się [4,7] . Zwracamy więc wartość bieżącego węzła (1) .
  Co najmniej dwie zwrócone wartości ( 2 , 1 ) to 1 . Aktualizujemy węzeł główny do 1 .

Nasze drzewo segmentu i drzewo leniwe wyglądałyby następująco:

Niezerowe wartości w węzłach naszego Lazy Tree reprezentują, istnieją aktualizacje oczekujące w tych węzłach i poniżej. W razie potrzeby zaktualizujemy je. Jeśli zostaniemy zapytani, jakie jest minimum w zakresie [0,3] , przejdziemy do lewego poddrzewa węzła głównego, a ponieważ nie ma oczekujących aktualizacji, zwrócimy 2 , co jest poprawne. Ten proces nie wpływa na poprawność naszego algorytmu drzewa segmentów.

przyrost [0,3] o 1:

Zaczynamy od węzła głównego. Brak oczekujących aktualizacji. [0,3] częściowo się pokrywa [0,7] . Idziemy w obie strony.
- W lewym poddrzewie nie ma oczekującej aktualizacji. [0,3] całkowicie pokrywa się [0,3] . Aktualizujemy aktualny węzeł: 2 + 1 = 3 . Ponieważ jest to wewnętrzny węzeł, aktualizujemy jego dzieci w Lazy Tree, aby zwiększyć je o 1 . Zwrócimy również wartość bieżącego węzła ( 3 ).
- W prawym poddrzewie nie ma oczekującej aktualizacji. [0,3] nie pokrywa się [4,7] . Zwracamy wartość bieżącego węzła ( 1 ).
Aktualizujemy węzeł główny, biorąc co najmniej dwie zwrócone wartości ( 3 , 1 ).

Nasze drzewo segmentu i drzewo leniwe będą wyglądać następująco:

Jak widać, gromadzimy aktualizacje w Lazy Tree, ale nie spychamy go w dół. To właśnie oznacza Leniwa propagacja. Gdybyśmy go nie użyli, musielibyśmy przesunąć wartości do liści, co kosztowałoby nas więcej niepotrzebnej złożoności czasu.

przyrost [0,0] o 2:

Zaczynamy od węzła głównego. Ponieważ root jest aktualny i [0,0] częściowo zachodzi na siebie [0,7] , kierujemy się w obu kierunkach.
- W lewym poddrzewie aktualny węzeł jest aktualny, a [0,0] częściowo się pokrywa [0,3] , kierujemy się w obu kierunkach.
  - W lewym poddrzewie bieżący węzeł Lazy Tree ma niezerową wartość. Jest więc aktualizacja, która nie została jeszcze propagowana do tego węzła. Najpierw zaktualizujemy ten węzeł w naszym drzewie segmentów. To staje się -1 + 4 = 3 . Następnie będziemy rozpowszechniać tę 4 wśród jej dzieci w Leniwym Drzewie. Ponieważ już zaktualizowaliśmy bieżący węzeł, zmienimy wartość bieżącego węzła w Lazy Tree na 0 . Następnie [0,0] częściowo zachodzi na [0,1] , więc idziemy w obu kierunkach.
    - W lewym węźle wartość musi zostać zaktualizowana, ponieważ w bieżącym węźle Lazy Tree występuje niezerowa wartość. Dlatego aktualizujemy wartość do -1 + 4 = 3 . Teraz, ponieważ [0,0] całkowicie pokrywa się z [0,0] , aktualizujemy wartość bieżącego węzła do 3 + 2 = 5 . Jest to węzeł liścia, więc nie musimy już propagować wartości. Aktualizujemy odpowiedni węzeł w Lazy Tree do 0, ponieważ wszystkie wartości zostały propagowane aż do tego węzła. Zwracamy wartość bieżącego węzła ( 5 ).
    - W prawym węźle wartość musi zostać zaktualizowana. Tak więc wartość staje się: 4 + 2 = 6 . Ponieważ [0,0] nie nakłada się na [1,1] , zwracamy wartość bieżącego węzła ( 6 ). Aktualizujemy również wartość w Lazy Tree do 0 . Nie jest wymagana propagacja, ponieważ jest to węzeł liścia.
      Aktualizujemy bieżący węzeł przy użyciu co najmniej dwóch zwracanych wartości ( 5 , 6 ). Zwracamy wartość bieżącego węzła ( 5 ).
  - W prawym poddrzewie oczekuje na aktualizację. Aktualizujemy wartość węzła do 1 + 4 = 5 . Ponieważ nie jest to węzeł liścia, propagujemy wartość do jego elementów podrzędnych w naszym Lazy Tree i aktualizujemy bieżący węzeł do 0 . Ponieważ [0,0] nie pokrywa się z [2,3] , zwracamy wartość naszego bieżącego węzła ( 5 ).
    Aktualizujemy bieżący węzeł przy użyciu minimum zwracanych wartości ( 5 , 5 ) i zwracamy wartość ( 5 ).
- W prawym poddrzewie nie ma oczekującej aktualizacji, a ponieważ [0,0] nie pokrywa się [4,7] , zwracamy wartość bieżącego węzła ( 1 ).
Aktualizujemy węzeł główny przy użyciu co najmniej dwóch zwracanych wartości ( 5 , 1 ).

Nasze drzewo segmentu i drzewo leniwe będą wyglądać następująco:

Możemy zauważyć, że w razie potrzeby wartość [0,0] otrzymała cały przyrost.

Teraz, jeśli zostaniesz poproszony o znalezienie minimum w zakresie [3,5] , jeśli zrozumiałeś do tego momentu, możesz łatwo dowiedzieć się, jak przebiegnie zapytanie, a zwrócona wartość wyniesie 1 . Nasz segment Tree i Lazy Tree wyglądałyby tak:

Po prostu zastosowaliśmy ten sam proces, który przeprowadziliśmy, szukając RMQ z dodatkowymi ograniczeniami sprawdzania Lazy Tree pod kątem oczekujących aktualizacji.

Inną rzeczą, którą możemy zrobić, to nie zwracać wartości z każdego węzła, ponieważ wiemy, co będzie węzłem potomnym naszego bieżącego węzła, możemy po prostu je sprawdzić, aby znaleźć minimum tych dwóch.

Pseudo-kod do aktualizacji w Lazy Propagation to:

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])

A pseudo-kod dla RMQ w Lazy Propagation będzie:

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

Licencjonowany na podstawie CC BY-SA 3.0

Nie związany z Stack Overflow

data-structures
Drzewo segmentów

Szukaj…

Wprowadzenie do drzewa segmentów

Implementacja drzewa segmentów za pomocą tablicy

Wykonywanie zapytania minimalnego zakresu

Leniwe propagowanie