data-structures
Segmentboom
Zoeken…
Inleiding tot segmentstructuur
Stel dat we een array hebben:
+-------+-----+-----+-----+-----+-----+-----+
| Index | 0 | 1 | 2 | 3 | 4 | 5 |
+-------+-----+-----+-----+-----+-----+-----+
| Value | -1 | 3 | 4 | 0 | 2 | 1 |
+-------+-----+-----+-----+-----+-----+-----+
We willen een query uitvoeren op deze array. Bijvoorbeeld:
- Wat is het minimum van index- 2 tot index- 4 ? -> 0
- Wat is het maximum van index- 0 tot index- 3 ? -> 4
- Wat is de samenvatting van index- 1 tot index- 5 ? -> 10
Hoe komen we erachter?
Brute kracht:
We kunnen de array doorlopen van de startindex naar de eindindex en onze vraag beantwoorden. In deze benadering duurt elke zoekopdracht O(n) tijd waarbij n het verschil is tussen de startindex en de eindindex. Maar wat als er miljoenen nummers en miljoenen vragen zijn? Voor m vragen zou het O(mn) tijd kosten. Dus voor 10⁵ waarden in onze array, als we 10⁵ query's uitvoeren, in het ergste geval, moeten we 10¹⁰ items doorlopen.
Dynamisch programmeren:
We kunnen een 6X6-matrix maken om de waarden voor verschillende bereiken op te slaan. Voor RMQ (range minimum query) ziet onze array er als volgt uit:
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 |
+-----+-----+-----+-----+-----+-----+-----+
Als we deze matrix eenmaal hebben opgebouwd, zou het voldoende zijn om alle RMQ's te beantwoorden. Hier slaat Matrix [i] [j] de minimumwaarde op van index- i tot index- j . Bijvoorbeeld: het minimum van index- 2 tot index- 4 is Matrix [2] [4] = 0 . Deze matrix beantwoordt de vraag in O(1) tijd, maar het kost O (n²) tijd om deze matrix en O(n²) ruimte te bouwen om het op te slaan. Dus als n een heel groot getal is, schaalt dit niet erg goed.
Segmentboom:
Een segmentboom is een boomgegevensstructuur voor het opslaan van intervallen of segmenten. Hiermee kunt u nagaan welke van de opgeslagen segmenten een bepaald punt bevatten. Het kost O(n) tijd om een segmentboom te bouwen, het kost O(n) ruimte om het te onderhouden en het beantwoordt een vraag in O(logn) tijd.
Segmentboom is een binaire boom en de elementen van de gegeven reeks zullen de bladeren van die boom zijn. We zullen de segmentboom maken door de array in twee te delen totdat we een enkel element bereiken. Dus onze divisie zou ons voorzien van:
Als we nu de niet-bladknopen vervangen door de minimale waarde van hun bladeren, krijgen we:
Dus dit is onze segmentboom. We kunnen opmerken dat het rootknooppunt de minimumwaarde van de hele array bevat (bereik [0,5]), het linkerkind de minimumwaarde van onze linkerarray bevat (bereik [0,2]), het rechterkind het minimum bevat waarde van onze juiste array (bereik [3,5]) enzovoort. De bladknooppunten bevatten de minimale waarde van elk afzonderlijk punt. We krijgen:
Laten we nu een bereikquery in deze boom uitvoeren. Om een bereikquery uit te voeren, moeten we drie voorwaarden controleren:
- Gedeeltelijke overlapping: we controleren beide bladeren.
- Totale overlapping: we retourneren de waarde die is opgeslagen in het knooppunt.
- Geen overlapping: we retourneren een zeer grote waarde of oneindig.
Laten we zeggen dat we bereik [2,4] willen controleren, wat betekent dat we het minimum van index- 2 tot 4 willen vinden. We beginnen bij de root en controleren of het bereik in onze knooppunten wordt overlapt door ons querybereik of niet. Hier,
- [2,4] overlapt niet volledig [0,5] . Dus we zullen beide richtingen controleren.
- Bij de linker subtree overlapt [ 2,4] gedeeltelijk [0,2] . We zullen beide richtingen controleren.
- Bij de linker subtree overlapt [2,4] [0,1] niet , dus dit gaat niet bijdragen aan ons antwoord. We keren oneindig terug.
- Rechtsonder overlapt [ 2,4] volledig [2,2] . We komen terug 4 .
Het minimum van deze twee geretourneerde waarden (4, oneindig) is 4 . We krijgen 4 van dit gedeelte.
- Rechtsonder overlapt [2,4] gedeeltelijk. Dus we zullen beide richtingen controleren.
- Bij de linker subtree overlapt [ 2,4] volledig [3,4] . We keren 0 terug.
- Rechtsonder overlapt [ 2,4] [5,5] niet . We keren oneindig terug.
Het minimum van deze twee geretourneerde waarden (0, oneindig) is 0 . We krijgen 0 uit dit gedeelte.
- Bij de linker subtree overlapt [ 2,4] gedeeltelijk [0,2] . We zullen beide richtingen controleren.
- Het minimum van de geretourneerde waarden (4,0) is 0 . Dit is ons gewenste minimum in bereik [2,4] .
Nu kunnen we controleren dat, ongeacht wat onze zoekopdracht is, er maximaal 4 stappen nodig zijn om de gewenste waarde uit deze segmentboom te vinden.
Gebruik:
- Bereik Minimale zoekopdracht
- Laagste gemeenschappelijke voorouder
- Luie voortplanting
- Dynamische Subtree Sum
- Verwaarlozing & Min
- Dubbele velden
- Het vinden van het kleinste element
- Aantal niet-geordende paren vinden
Implementatie van segmentstructuur met behulp van array
Laten we zeggen dat we een array hebben: Item = {-1, 0, 3, 6} . We willen een SegmentTree- array maken om de minimumwaarde in een bepaald bereik te achterhalen. Onze segmentboom ziet eruit als:
De getallen onder de knooppunten tonen de indices van elke waarden die we opslaan in onze SegmentTree- array. We kunnen zien dat we, om 4 elementen op te slaan, een array van maat 7 nodig hadden. Deze waarde wordt bepaald door:
Procedure DetermineArraySize(Item):
multiplier := 1
n := Item.size
while multiplier < n
multiplier := multiplier * 2
end while
size := (2 * multiplier) - 1
Return size
Dus als we een array met lengte 5 hadden, zou de grootte van onze SegmentTree- array zijn: ( 8 * 2 ) - 1 = 15 . Om nu de positie van het linker en rechter kind van een knoop te bepalen, als een knoop in index i staat , dan is de positie van zijn:
- Linkerkind wordt aangeduid met: (2 * i) + 1 .
- Rechts kind wordt aangeduid met: (2 * i) + 2 .
En de index van de ouder van een willekeurig knooppunt in index i kan worden bepaald door: (i - 1) / 2 .
Dus de SegmentTree- array die ons voorbeeld vertegenwoordigt, ziet er als volgt uit:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+
| -1 | -1 | 3 | -1 | 0 | 3 | 6 |
+-----+-----+-----+-----+-----+-----+-----+
Laten we de pseudo-code bekijken om deze array te construeren:
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
Eerst nemen we de invoer van de waarden over en initialiseren we de SegmentTree- array met infinity met behulp van de lengte van de Item- array als zijn grootte. We noemen de procedure met behulp van:
- lage = beginindex Punt array.
- hoog = Afwerking index van punt array.
- position = 0, geeft de root van onze segmentboom aan.
Laten we nu proberen de procedure te begrijpen met behulp van een voorbeeld: 
De grootte van onze Item- array is 4 . We maken een array van lengte (4 * 2) - 1 = 7 en initialiseren ze met infinity . Je kunt er een heel grote waarde voor gebruiken. Onze reeks ziet er als volgt uit:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+
| inf | inf | inf | inf | inf | inf | inf |
+-----+-----+-----+-----+-----+-----+-----+
Aangezien dit een recursieve procedure, zullen we de werking van het zien ConstructTree met behulp van een recursietabel dat bijhoudt blijft low , high , position , mid en calling line bij elk gesprek. Eerst noemen we ConstructTree (Artikel, SegmentTree, 0, 3, 0) . Hier is low niet hetzelfde als high , we krijgen een mid . De calling line geeft aan welke ConstructTree na deze instructie wordt genoemd. We duiden de ConstructTree aanroepen binnen de procedure aan als respectievelijk 1 en 2 . Onze tafel ziet eruit als:
+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
| 0 | 3 | 0 | 1 | 1 |
+-----+------+----------+-----+--------------+
Dus als we ConstructTree-1 aanroepen, passeren we: low = 0 , high = mid = 1 , position = 2*position+1 = 2*0+1 = 1 . Een ding dat je kunt opmerken, dat is 2*position+1 is het linkerkind van root , dat is 1 . Omdat low niet gelijk is aan high , krijgen we een mid . Onze tafel ziet eruit als:
+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
| 0 | 3 | 0 | 1 | 1 |
+-----+------+----------+-----+--------------+
| 0 | 1 | 1 | 0 | 1 |
+-----+------+----------+-----+--------------+
In de volgende recursieve aanroep passeren we low = 0 , high = mid = 0 , position = 2*position+1 = 2*1+1=3 . Opnieuw is het linkerkind van index 1 3 . Hier is low e high , dus stellen we SegmentTree[position] = SegmentTree[3] = Item[low] = Item[0] = -1 . Onze SegmentTree- array ziet eruit als:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+
| inf | inf | inf | -1 | inf | inf | inf |
+-----+-----+-----+-----+-----+-----+-----+
Onze recursietabel ziet eruit als:
+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
| 0 | 3 | 0 | 1 | 1 |
+-----+------+----------+-----+--------------+
| 0 | 1 | 1 | 0 | 1 |
+-----+------+----------+-----+--------------+
| 0 | 0 | 3 | | |
+-----+------+----------+-----+--------------+
Je ziet dus dat -1 de juiste positie heeft. Aangezien deze recursieve oproep is voltooid, gaan we terug naar de vorige rij van onze recursietabel. De tafel:
+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
| 0 | 3 | 0 | 1 | 1 |
+-----+------+----------+-----+--------------+
| 0 | 1 | 1 | 0 | 1 |
+-----+------+----------+-----+--------------+
In onze procedure voeren we de ConstructTree-2 aanroep uit. Deze keer passeren we low = mid+1 = 1 , high = 1 , position = 2*position+2 = 2*1+2 = 4 . Onze calling line verandert in 2 . We krijgen:
+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
| 0 | 3 | 0 | 1 | 1 |
+-----+------+----------+-----+--------------+
| 0 | 1 | 1 | 0 | 2 |
+-----+------+----------+-----+--------------+
Omdat low gelijk is aan high , stellen we in: SegmentTree[position] = SegmentTree[4] = Item[low] = Item[1] = 2 . Onze SegmentTree- reeks:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+
| inf | inf | inf | -1 | 2 | inf | inf |
+-----+-----+-----+-----+-----+-----+-----+
Onze recursietabel:
+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
| 0 | 3 | 0 | 1 | 1 |
+-----+------+----------+-----+--------------+
| 0 | 1 | 1 | 0 | 2 |
+-----+------+----------+-----+--------------+
| 1 | 1 | 4 | | |
+-----+------+----------+-----+--------------+
Nogmaals zie je, 2 heeft de juiste positie. Na dit recursieve gesprek gaan we terug naar de vorige rij van onze recursietabel. We krijgen:
+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
| 0 | 3 | 0 | 1 | 1 |
+-----+------+----------+-----+--------------+
| 0 | 1 | 1 | 0 | 2 |
+-----+------+----------+-----+--------------+
We voeren de laatste regel van onze procedure uit, SegmentTree[position] = SegmentTree[1] = min(SegmentTree[2*position+1], SegmentTree[2*position+2]) = min(SegmentTree[3], SegmentTree[4]) = min(-1,2) = -1 . Onze SegmentTree- reeks:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+
| inf | -1 | inf | -1 | 2 | inf | inf |
+-----+-----+-----+-----+-----+-----+-----+
Aangezien deze recursie-oproep is voltooid, gaan we terug naar de vorige rij van onze recursietabel en roepen ConstructTree-2 :
+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
| 0 | 3 | 0 | 1 | 2 |
+-----+------+----------+-----+--------------+
We kunnen zien dat het linker gedeelte van onze segmentboom compleet is. Als we op deze manier doorgaan, krijgen we na het voltooien van de hele procedure eindelijk een voltooide SegmentTree- array, die eruit ziet als:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+
| -1 | -1 | 0 | -1 | 2 | 4 | 0 |
+-----+-----+-----+-----+-----+-----+-----+
De tijd- en ruimtecomplexiteit van het construeren van deze SegmentTree- array is: O(n) , waarbij n het aantal elementen in Item- array aangeeft. Onze geconstrueerde SegmentTree- array kan worden gebruikt om Range Minimum Query (RMQ) uit te voeren . Om een array te construeren om Range Maximum Query uit te voeren, moeten we de regel vervangen:
SegmentTree[position] := min(SegmentTree[2*position+1], SegmentTree[2*position+2])
met:
SegmentTree[position] := max(SegmentTree[2*position+1], SegmentTree[2*position+2])
Een bereik uitvoeren Minimale zoekopdracht
De procedure voor het uitvoeren van een RMQ is al in de inleiding getoond. De pseudo-code voor het controleren van Bereik Minimale zoekopdracht is:
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
Hier, 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 . Laten we nu proberen de procedure te begrijpen aan de hand van het voorbeeld dat we eerder hebben gemaakt:
Onze SegmentTree- reeks:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+
| -1 | -1 | 0 | -1 | 2 | 4 | 0 |
+-----+-----+-----+-----+-----+-----+-----+
We willen het minimum in bereik [1,3] vinden .
Aangezien dit een recursieve procedure is, zien we de werking van de RangeMinimumQuery met behulp van een recursietabel die qLow , qHigh , low , high , position , mid en calling line qHigh . In eerste instantie, we RangeMinimumQuery (SegmentTree, 1, 3, 0, 3, 0 noemen. Hier zijn de eerste twee voorwaarden niet is voldaan (gedeeltelijke overlap). We zullen een krijgen mid . De calling line geeft aan welke RangeMinimumQuery is genoemd naar deze We duiden de RangeMinimumQuery aanroepen binnen de procedure aan als respectievelijk 1 en 2. Onze tabel ziet eruit als:
+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 0 | 3 | 0 | 1 | 1 |
+------+-------+-----+------+----------+-----+--------------+
Dus als we RangeMinimumQuery-1 aanroepen, passeren we: low = 0 , high = mid = 1 , position = 2*position+1 = 1 . Een ding dat je kunt opmerken, dat is 2*position+1 is het linkerkind van een knooppunt . Dat betekent dat we het linkerkind van root controleren . Omdat [1,3] [0,1 ] gedeeltelijk overlapt, wordt niet aan de eerste twee voorwaarden voldaan, we krijgen een mid . Onze tafel:
+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 0 | 3 | 0 | 1 | 1 |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 0 | 1 | 1 | 0 | 1 |
+------+-------+-----+------+----------+-----+--------------+
In de volgende recursieve aanroep passeren we low = 0 , high = mid = 0 , position = 2*position+1 = 3 . We bereiken het meest linkse blad van onze boom. Omdat [1,3] niet overlapt met [0,0] , keren we infinity terug naar onze roepfunctie. Recursietabel:
+------+-------+-----+------+----------+-----+--------------+
| 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 | | |
+------+-------+-----+------+----------+-----+--------------+
Aangezien deze recursieve oproep is voltooid, gaan we terug naar de vorige rij van onze recursietabel. We krijgen:
+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 0 | 3 | 0 | 1 | 1 |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 0 | 1 | 1 | 0 | 1 |
+------+-------+-----+------+----------+-----+--------------+
In onze procedure voeren we de RangeMinimumQuery-2 aanroep uit. Deze keer passeren we low = mid+1 = 1 , high = 1 en position = 2*position+2 = 4 . Onze calling line changes to **2** . We krijgen:
+------+-------+-----+------+----------+-----+--------------+
| 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 | | |
+------+-------+-----+------+----------+-----+--------------+
Dus we gaan naar het juiste kind van het vorige knooppunt. Deze keer is er een totale overlap. We retourneren de waarde SegmentTree[position] = SegmentTree[4] = 2 .
+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 0 | 3 | 0 | 1 | 1 |
+------+-------+-----+------+----------+-----+--------------+
Terug bij de aanroepfunctie controleren we wat het minimum is van de twee geretourneerde waarden van twee aanroepfuncties. Uiteraard is het minimum 2 , we keren 2 terug naar de aanroepfunctie. Onze recursietabel ziet eruit als:
+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 0 | 3 | 0 | 1 | 1 |
+------+-------+-----+------+----------+-----+--------------+
We zijn klaar met kijken naar het linker gedeelte van onze segmentboom. Nu zullen we RangeMinimumQuery-2 vanaf hier bellen. We passeren low = mid+1 = 1+1 =2 , high = 3 en position = 2*position+2 = 2 . Onze tafel:
+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 0 | 3 | 0 | 1 | 1 |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 2 | 3 | 2 | | |
+------+-------+-----+------+----------+-----+--------------+
Er is een totale overlap. Dus we geven de waarde terug: SegmentTree[position] = SegmentTree[2] = 0 . We komen terug op de recursie van waar deze twee kinderen werden genoemd en krijgen het minimum van (4,0) , dat is 0 en geven de waarde terug.
Na het uitvoeren van de procedure krijgen we 0 , wat het minimum is van index- 1 tot index- 3 .
De runtime-complexiteit voor deze procedure is O(logn) waarbij n het aantal elementen in de Items- array is. Om een bereik maximale zoekopdracht uit te voeren, moeten we de regel vervangen:
Return min(RangeMinimumQuery(SegmentTree, qLow, qHigh, low, mid, 2*position+1),
RangeMinimumQuery(SegmentTree, qLow, qHigh, mid+1, high, 2*position+2))
met:
Return max(RangeMinimumQuery(SegmentTree, qLow, qHigh, low, mid, 2*position+1),
RangeMinimumQuery(SegmentTree, qLow, qHigh, mid+1, high, 2*position+2))
Luie voortplanting
Stel dat u al een segmentboom hebt gemaakt. U moet de waarden van de array bijwerken, dit zal niet alleen de bladknooppunten van uw segmentboom wijzigen, maar ook het minimum / maximum in sommige knooppunten. Laten we dit eens bekijken met een voorbeeld:
Dit is onze minimale segmentboom van 8 elementen. Om u een snelle herinnering te geven, vertegenwoordigen elke knooppunten de minimumwaarde van het bereik dat naast hen wordt vermeld. Laten we zeggen dat we de waarde van het eerste item van onze array met 3 willen verhogen. Hoe kunnen we dat doen? We volgen de manier waarop we RMQ hebben uitgevoerd. Het proces ziet er als volgt uit:
- In eerste instantie doorkruisen we de wortel. [0,0] overlapt gedeeltelijk met [0,7] , we gaan naar beide richtingen.
- Bij de linker subtree, [0,0] overlapt gedeeltelijk met [0,3] , gaan we naar beide richtingen.
- Bij de linker subtree, [0,0] overlapt gedeeltelijk met [0,1] , gaan we naar beide richtingen.
- Bij de linker subtree overlapt [0,0] volledig met [0,0] , en omdat het de bladknoop is, werken we de knoop bij door de waarde met 3 te verhogen. En retourneer de waarde -1 + 3 = 2 .
- Bij de juiste substructuur overlapt [1,1] niet met [0,0] , we geven de waarde terug bij het knooppunt ( 2 ).
Het minimum van deze twee geretourneerde waarden ( 2 , 2 ) is 2 , dus we werken de waarde van het huidige knooppunt bij en retourneren deze.
- Rechts subboom [2,3] overlapt niet met [0,0] , we geven de waarde van de knoop terug. ( 1 ).
Aangezien het minimum van deze twee geretourneerde waarden ( 2 , 1 ) 1 is , werken we de waarde van het huidige knooppunt bij en retourneren deze.
- Bij de linker subtree, [0,0] overlapt gedeeltelijk met [0,1] , gaan we naar beide richtingen.
- Rechts subboom [4,7] overlapt niet met [0,0] , we geven de waarde van de knoop terug. ( 1 ).
- Bij de linker subtree, [0,0] overlapt gedeeltelijk met [0,3] , gaan we naar beide richtingen.
- Ten slotte wordt de waarde van het hoofdknooppunt bijgewerkt, omdat het minimum van de twee geretourneerde waarden (1,1) 1 is .
We kunnen zien dat het bijwerken van een enkel knooppunt O(logn) tijdcomplexiteit vereist, waarbij n het aantal bladknooppunten is. Dus als ons wordt gevraagd om enkele knooppunten van i tot j bij te werken , hebben we O(nlogn) tijdcomplexiteit nodig. Dit wordt omslachtig voor een grote waarde van n . Laten we lui zijn , dus werk alleen wanneer dat nodig is. Hoe? Wanneer we een interval moeten bijwerken, zullen we een knooppunt bijwerken en het onderliggende item markeren dat het moet worden bijgewerkt en indien nodig bijwerken. Hiervoor hebben we een reeks lui nodig van dezelfde grootte als die van een segmentboom. Aanvankelijk zijn alle elementen van de luie array 0, wat betekent dat er geen update in behandeling is. Als er een niet-nul-element in lui [i] staat , moet dit element knooppunt i in de segmentstructuur bijwerken voordat u querybewerkingen uitvoert. Hoe gaan we dat doen? Laten we een voorbeeld bekijken:
Laten we zeggen dat we voor onze voorbeeldboom enkele vragen willen uitvoeren. Dit zijn:
- toename [0,3] met 3 .
- toename [0,3] met 1 .
- toename [0,0] met 2 .
toename [0,3] met 3:
We starten vanuit het root-knooppunt. Eerst controleren we of deze waarde actueel is. Hiervoor controleren we onze luie array die 0 is , wat betekent dat de waarde up-to-date is. [0,3] overlapt gedeeltelijk [0,7] . Dus gaan we naar beide richtingen.
- Aan de linker subtree is er geen update in behandeling. [0,3] overlapt volledig [0,3] . Dus werken we de waarde van het knooppunt met 3 bij . De waarde wordt dus -1 + 3 = 2 . Deze keer gaan we niet helemaal. In plaats van naar beneden te gaan, werken we het bijbehorende kind in de luie boom van onze huidige knoop bij en verhogen we ze met 3 . We retourneren ook de waarde van het huidige knooppunt.
- Op de juiste subtree is er geen update in behandeling. [0,3] overlapt niet [4,7] . Dus we retourneren de waarde van het huidige knooppunt (1) .
Het minimum van twee geretourneerde waarden ( 2 , 1 ) is 1 . We werken het root-knooppunt bij naar 1 .
Onze segmentboom en luie boom zouden er als volgt uitzien:
De niet-nulwaarden in knooppunten van onze Lazy Tree vertegenwoordigen, er zijn updates in behandeling in die knooppunten en lager. We zullen ze indien nodig bijwerken. Als ons wordt gevraagd wat het minimum in bereik [0,3] is , komen we aan de linkersubboom van de root-node en omdat er geen updates in behandeling zijn, zullen we 2 retourneren, wat correct is. Dit proces heeft dus geen invloed op de juistheid van ons segmentboomalgoritme.
toename [0,3] met 1:
- We starten vanuit het root-knooppunt. Er is geen update in behandeling. [0,3] overlapt gedeeltelijk [0,7] . Dus gaan we naar beide richtingen.
- In de linkersubboom is er geen update in behandeling. [0,3] overlapt volledig [0,3] . We werken het huidige knooppunt bij: 2 + 1 = 3 . Omdat dit een intern knooppunt is, werken we de kinderen in de Lazy Tree bij met 1 . We retourneren ook de waarde van het huidige knooppunt ( 3 ).
- In de juiste subtree is er geen update in behandeling. [0,3] overlapt niet [4,7] . We retourneren de waarde van het huidige knooppunt ( 1 ).
- We werken het root-knooppunt bij door minimaal twee geretourneerde waarden te nemen ( 3 , 1 ).
Onze Segment Tree en Lazy Tree zien eruit als:
Zoals je kunt zien, verzamelen we de updates bij Lazy Tree maar duwen we deze niet omlaag. Dit is wat Lazy Propagation betekent. Als we het niet hadden gebruikt, moesten we de waarden tot het einde duwen, wat ons meer onnodige tijdcomplexiteit zou kosten.
toename [0,0] met 2:
- We starten vanuit het root-knooppunt. Omdat root up-to-date is en [0,0] [0,7] gedeeltelijk overlapt, gaan we naar beide richtingen.
- Aan de linker substructuur is het huidige knooppunt actueel en overlapt [ 0,0] gedeeltelijk [0,3] , we gaan naar beide richtingen.
- Aan de linker subtree heeft het huidige knooppunt in Lazy Tree een niet-nulwaarde. Er is dus een update die nog niet naar dit knooppunt is doorgegeven. We gaan dit knooppunt eerst bijwerken in onze segmentstructuur. Dus dit wordt -1 + 4 = 3 . Dan gaan we deze 4 verspreiden naar zijn kinderen in de Lazy Tree. Omdat we het huidige knooppunt al hebben bijgewerkt, zullen we de waarde van het huidige knooppunt in Lazy Tree wijzigen in 0 . Dan overlapt [0,0] [0,1] gedeeltelijk , dus we gaan naar beide richtingen.
- Bij het linkerknooppunt moet de waarde worden bijgewerkt, omdat er een niet-nulwaarde in het huidige knooppunt van Lazy Tree is. Dus werken we de waarde bij naar -1 + 4 = 3 . Daar nu [0,0] geheel overlapt [0,0], updaten we de waarde van het huidige knooppunt 3 + 2 = 5. Dit is een bladknooppunt, dus we hoeven de waarde niet meer te verspreiden. We werken het overeenkomstige knooppunt bij de Lazy Tree bij naar 0, omdat alle waarden tot dit knooppunt zijn doorgevoerd. We retourneren de waarde van het huidige knooppunt ( 5 ).
- Bij het juiste knooppunt moet de waarde worden bijgewerkt. De waarde wordt dus: 4 + 2 = 6 . Omdat [0,0] [1,1] niet overlapt, retourneren we de waarde van het huidige knooppunt ( 6 ). We werken ook de waarde in Lazy Tree bij naar 0 . Er is geen propagatie nodig omdat dit een bladknoop is.
We werken het huidige knooppunt bij met minimaal twee geretourneerde waarden ( 5 , 6 ). We retourneren de waarde van het huidige knooppunt ( 5 ).
- Aan de juiste substructuur is er een update in behandeling. We werken de waarde van het knooppunt bij naar 1 + 4 = 5 . Omdat dit geen bladknooppunt is, verspreiden we de waarde naar de onderliggende waarden in onze Lazy Tree en werken we het huidige knooppunt bij naar 0 . Omdat [0,0] niet overlapt met [2,3] , retourneren we de waarde van onze huidige knoop ( 5 ).
We werken het huidige knooppunt bij met behulp van het minimum van de geretourneerde waarden ( 5 , 5 ) en retourneren de waarde ( 5 ).
- Aan de linker subtree heeft het huidige knooppunt in Lazy Tree een niet-nulwaarde. Er is dus een update die nog niet naar dit knooppunt is doorgegeven. We gaan dit knooppunt eerst bijwerken in onze segmentstructuur. Dus dit wordt -1 + 4 = 3 . Dan gaan we deze 4 verspreiden naar zijn kinderen in de Lazy Tree. Omdat we het huidige knooppunt al hebben bijgewerkt, zullen we de waarde van het huidige knooppunt in Lazy Tree wijzigen in 0 . Dan overlapt [0,0] [0,1] gedeeltelijk , dus we gaan naar beide richtingen.
- Op de juiste substructuur is er geen update in behandeling en omdat [0,0] [4,7] niet overlapt, retourneren we de waarde van het huidige knooppunt ( 1 ).
- Aan de linker substructuur is het huidige knooppunt actueel en overlapt [ 0,0] gedeeltelijk [0,3] , we gaan naar beide richtingen.
- We werken het rootknooppunt bij met behulp van het minimum van de twee geretourneerde waarden ( 5 , 1 ).
Onze Segment Tree en Lazy Tree zien eruit als:
We kunnen opmerken dat de waarde op [0,0] , indien nodig, alle stappen kreeg.
Nu als u wordt gevraagd om de minimum binnen het bereik [3,5] te vinden, als je je hebt begrepen op dit punt, kunt u eenvoudig achterhalen hoe de query zou gaan en de geretourneerde waarde zal zijn 1. Ons segment Tree en Lazy Tree ziet eruit als:
We hebben eenvoudigweg hetzelfde proces gevolgd dat we hebben gevolgd bij het vinden van RMQ met toegevoegde beperkingen van het controleren van de Lazy Tree op in afwachting van updates.
Een ander ding dat we kunnen doen is in plaats van het retourneren van waarden uit elk knooppunt, omdat we weten wat het onderliggende knooppunt van onze huidige knoop zal zijn, kunnen we ze eenvoudig controleren om het minimum van deze twee te vinden.
De pseudo-code voor bijwerken in Lazy Propagation zou zijn:
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])
En de pseudo-code voor RMQ in Lazy Propagation zal zijn:
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)