data-structures
Segmentträd
Sök…
Introduktion till segmentträd
Anta att vi har en matris:
+-------+-----+-----+-----+-----+-----+-----+
| Index | 0 | 1 | 2 | 3 | 4 | 5 |
+-------+-----+-----+-----+-----+-----+-----+
| Value | -1 | 3 | 4 | 0 | 2 | 1 |
+-------+-----+-----+-----+-----+-----+-----+
Vi vill utföra en fråga i den här matrisen. Till exempel:
- Vad är lägsta från index- 2 till index- 4 ? -> 0
- Vad är det maximala från index- 0 till index- 3 ? -> 4
- Vad är summeringen från index- 1 till index- 5 ? -> 10
Hur hittar vi det?
Råstyrka:
Vi kan korsa matrisen från startindex till slutindex och besvara vår fråga. I detta tillvägagångssätt tar varje fråga O(n) tid där n är skillnaden mellan startindex och slutindex. Men vad händer om det finns miljoner nummer och miljoner frågor? För m frågor, skulle det ta O(mn) tid. Så för 10⁵-värden i vår grupp, om vi gör 10⁵-frågor, i värsta fall, måste vi korsa 10¹⁰ artiklar.
Dynamisk programmering:
Vi kan skapa en 6X6-matris för att lagra värdena för olika intervall. För intervallminsta fråga (RMQ) ser vår matris ut som:
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 |
+-----+-----+-----+-----+-----+-----+-----+
När vi har fått denna matrisbyggnad, räcker det att svara på alla RMQ: er. Här skulle Matrix [i] [j] lagra minimivärdet från index- i till index- j . Exempel: Minsta från index- 2 till index- 4 är Matrix [2] [4] = 0 . Denna matris svarar på frågan i O(1) -tid, men det tar O (n²) tid att bygga denna matris och O(n²) utrymme att lagra den. Så om n är ett riktigt stort antal, skalas det inte så bra.
Segmentträd:
Ett segmentträd är en träddatastruktur för lagring av intervaller eller segment. Det tillåter fråga vilka av de lagrade segmenten som innehåller en given punkt. Det tar O(n) tid att bygga ett segmentträd, det tar O(n) utrymme att underhålla det och det svarar på en fråga i O(logn) .
Segmentträd är ett binärt träd och elementen i den givna arrayen är bladen på det trädet. Vi skapar segmentträdet genom att dela matrisen i halva tills vi når ett enda element. Så vår division skulle ge oss:
Om vi nu ersätter de icke-bladnoderna med minsta värde på deras blad, får vi:
Så detta är vårt segmentträd. Vi kan märka att rotnoden innehåller minimivärdet för hela matrisen (intervall [0,5]), dess vänstra barn innehåller minimivärdet för vår vänstra matris (intervall [0,2]), det högra barnet innehåller det minsta värdet på vår högra array (intervall [3,5]) och så vidare. Bladnoderna innehåller minimivärdet för varje enskild poäng. Vi får:
Låt oss nu göra en intervallfråga på det här trädet. För att göra en intervallfråga måste vi kontrollera tre villkor:
- Delvis överlappning: Vi kontrollerar båda bladen.
- Total överlappning: Vi returnerar värdet lagrat i noden.
- Ingen överlappning: Vi returnerar ett mycket stort värde eller oändlighet.
Låt oss säga, vi vill kontrollera intervallet [2,4] , det betyder att vi vill hitta minimum från index- 2 till 4 . Vi börjar från roten och kontrollerar om intervallet i våra noder är överlappat av vårt frågeställning eller inte. Här,
- [2,4] överlappar inte helt [0,5] . Så vi kontrollerar båda riktningarna.
- Vid vänster underträna överlappar [ 2,4] delvis [0,2] . Vi kontrollerar båda riktningarna.
- På vänster undertråd överlappar [2,4] inte [0,1] , så detta kommer inte att bidra till vårt svar. Vi återvänder oändligheten .
- Till höger underträde överlappar [ 2,4] totalt [2,2] . Vi återvänder 4 .
Minsta av dessa två returnerade värden (4, oändlighet) är 4 . Vi får 4 från den här delen.
- Till höger underträde överlappar delvis [2,4] . Så vi kontrollerar båda riktningarna.
- På vänster underträna överlappar [ 2,4] fullständigt [3,4] . Vi återlämnar 0 .
- På höger underträda överlappar [ 2,4] inte [5,5] . Vi återvänder oändligheten .
Minsta av dessa två returnerade värden (0, oändlighet) är 0 . Vi får 0 från den här delen.
- Vid vänster underträna överlappar [ 2,4] delvis [0,2] . Vi kontrollerar båda riktningarna.
- Minsta antal returnerade värden (4,0) är 0 . Detta är vårt önskade minimum inom intervallet [2,4] .
Nu kan vi kontrollera att oavsett vår fråga, det skulle ta högst fyra steg för att hitta önskat värde från detta segmentträd.
Använda sig av:
- Område Minsta fråga
- Lägsta vanliga förfader
- Lat förökning
- Dynamisk underträngssumma
- Försummelse & Min
- Dubbla fält
- Hitta k-th Minsta element
- Hitta antal oordnade par
Implementering av segmentträd med array
Låt oss säga, vi har en matris: Item = {-1, 0, 3, 6} . Vi vill konstruera SegmentTree- array för att ta reda på minimivärdet i ett visst intervall. Vårt segmentträd kommer att se ut:
Siffrorna under noderna visar index för alla värden som vi lagrar i vårt segment SegmentTree . Vi kan se att för att lagra fyra element behövde vi en matris med storlek 7. Detta värde bestäms av:
Procedure DetermineArraySize(Item):
multiplier := 1
n := Item.size
while multiplier < n
multiplier := multiplier * 2
end while
size := (2 * multiplier) - 1
Return size
Så om vi hade en matris med längd 5 skulle storleken på vårt SegmentTree- array vara: ( 8 * 2 ) - 1 = 15 . För att bestämma positionen för vänster och höger barn i en nod, om en nod är i index i , då är positionen för dess:
- Left Child betecknas med: (2 * i) + 1 .
- Rätt barn betecknas med: (2 * i) + 2 .
Och indexet för överordnade till någon nod i index i kan bestämmas av: (i - 1) / 2 .
Så SegmentTree- arrayen som representerar vårt exempel skulle se ut:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+
| -1 | -1 | 3 | -1 | 0 | 3 | 6 |
+-----+-----+-----+-----+-----+-----+-----+
Låt oss titta på pseudokoden för att konstruera denna matris:
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
Till att börja med tar vi in värdena och initialiserar SegmentTree- matrisen med infinity använda längden på artikelgruppen som dess storlek. Vi kallar proceduren med hjälp av:
- låg = Startindex för artikeluppsättningen .
- high = Efterbehandlingsindex för artikeluppsättningen .
- position = 0, indikerar roten till vårt segmentträd.
Låt oss försöka förstå proceduren med hjälp av ett exempel: 
Storleken på vår artikelgrupp är 4 . Vi skapar en matris med längd (4 * 2) - 1 = 7 och initialiserar dem med infinity . Du kan använda ett mycket stort värde för det. Vår matris skulle se ut:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+
| inf | inf | inf | inf | inf | inf | inf |
+-----+-----+-----+-----+-----+-----+-----+
Eftersom detta är en rekursiv procedur, vi får se driften av ConstructTree med hjälp av en rekursion bord som håller koll på low , high , position , mid och calling line vid varje samtal. Till att börja med kallar vi ConstructTree (Item, SegmentTree, 0, 3, 0) . Här är low inte samma som high , vi får en mid . calling line anger vilken ConstructTree kallas efter detta uttalande. Vi anger ConstructTree samtal inom proceduren som 1 respektive 2 . Vårt bord kommer att se ut som:
+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
| 0 | 3 | 0 | 1 | 1 |
+-----+------+----------+-----+--------------+
Så när vi kallar ConstructTree-1 passerar vi: low = 0 , high = mid = 1 , position = 2*position+1 = 2*0+1 = 1 . En sak du kan märka, det vill säga 2*position+1 är det vänstra barnet med roten , vilket är 1 . Eftersom low inte är lika high , får vi en mid . Vårt bord kommer att se ut som:
+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
| 0 | 3 | 0 | 1 | 1 |
+-----+------+----------+-----+--------------+
| 0 | 1 | 1 | 0 | 1 |
+-----+------+----------+-----+--------------+
I nästa rekursiva samtal passerar vi low = 0 , high = mid = 0 , position = 2*position+1 = 2*1+1=3 . Återigen är det vänstra barnet i index 1 3 . Här är low e high , så vi ställer in SegmentTree[position] = SegmentTree[3] = Item[low] = Item[0] = -1 . Vår SegmentTree- serie kommer att se ut:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+
| inf | inf | inf | -1 | inf | inf | inf |
+-----+-----+-----+-----+-----+-----+-----+
Vår rekursionstabell kommer att se ut som:
+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
| 0 | 3 | 0 | 1 | 1 |
+-----+------+----------+-----+--------------+
| 0 | 1 | 1 | 0 | 1 |
+-----+------+----------+-----+--------------+
| 0 | 0 | 3 | | |
+-----+------+----------+-----+--------------+
Så du kan se, -1 har sin korrekta position. Eftersom detta rekursiva samtal är slutfört, går vi tillbaka till föregående rad i vårt rekursionstabell. Bordet:
+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
| 0 | 3 | 0 | 1 | 1 |
+-----+------+----------+-----+--------------+
| 0 | 1 | 1 | 0 | 1 |
+-----+------+----------+-----+--------------+
I vårt förfarande utför vi samtalet ConstructTree-2 . Den här gången passerar vi low = mid+1 = 1 , high = 1 , position = 2*position+2 = 2*1+2 = 4 . Vår calling line ändras till 2 . Vi får:
+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
| 0 | 3 | 0 | 1 | 1 |
+-----+------+----------+-----+--------------+
| 0 | 1 | 1 | 0 | 2 |
+-----+------+----------+-----+--------------+
Eftersom, low är lika med high , ställer vi in: SegmentTree[position] = SegmentTree[4] = Item[low] = Item[1] = 2 . Vårt SegmentTree- array:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+
| inf | inf | inf | -1 | 2 | inf | inf |
+-----+-----+-----+-----+-----+-----+-----+
Vår rekursionstabell:
+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
| 0 | 3 | 0 | 1 | 1 |
+-----+------+----------+-----+--------------+
| 0 | 1 | 1 | 0 | 2 |
+-----+------+----------+-----+--------------+
| 1 | 1 | 4 | | |
+-----+------+----------+-----+--------------+
Återigen kan du se, 2 har rätt position. Efter detta rekursiva samtal går vi tillbaka till föregående rad i vårt rekursionstabell. Vi får:
+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
| 0 | 3 | 0 | 1 | 1 |
+-----+------+----------+-----+--------------+
| 0 | 1 | 1 | 0 | 2 |
+-----+------+----------+-----+--------------+
Vi kör den sista raden i vårt förfarande, SegmentTree[position] = SegmentTree[1] = min(SegmentTree[2*position+1], SegmentTree[2*position+2]) = min(SegmentTree[3], SegmentTree[4]) = min(-1,2) = -1 . Vårt SegmentTree- array:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+
| inf | -1 | inf | -1 | 2 | inf | inf |
+-----+-----+-----+-----+-----+-----+-----+
Eftersom detta rekursionssamtal är slutfört går vi tillbaka till föregående rad i vår rekursionstabell och ringer ConstructTree-2 :
+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
| 0 | 3 | 0 | 1 | 2 |
+-----+------+----------+-----+--------------+
Vi kan se att den vänstra delen av vårt segmentträd är komplett. Om vi fortsätter på det här sättet, efter att ha slutfört hela proceduren, kommer vi äntligen att få en färdig SegmentTree- array, så kommer det att se ut:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+
| -1 | -1 | 0 | -1 | 2 | 4 | 0 |
+-----+-----+-----+-----+-----+-----+-----+
Tids- och rymdkomplexiteten för att konstruera denna SegmentTree- matris är: O(n) , där n anger antalet element i artikelgrupp . Vår konstruerade SegmentTree- array kan användas för att utföra Range Minimum Query (RMQ) . För att konstruera en matris för att utföra Range Maximum Query , måste vi ersätta linjen:
SegmentTree[position] := min(SegmentTree[2*position+1], SegmentTree[2*position+2])
med:
SegmentTree[position] := max(SegmentTree[2*position+1], SegmentTree[2*position+2])
Utföra en intervallminsta fråga
Proceduren för att utföra en RMQ visas redan i introduktionen. Pseudokoden för att kontrollera intervallet Minsta fråga är:
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
Här 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 . Låt oss nu försöka förstå proceduren med det exempel vi skapade tidigare:
Vårt SegmentTree- array:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+
| -1 | -1 | 0 | -1 | 2 | 4 | 0 |
+-----+-----+-----+-----+-----+-----+-----+
Vi vill hitta det minsta inom intervallet [1,3] .
Eftersom detta är en rekursiv procedur ser vi funktionen för RangeMinimumQuery hjälp av en rekursionstabell som håller reda på qLow , qHigh , low , high , position , mid och calling line . Först vi kallar RangeMinimumQuery (SegmentTree, 1, 3, 0, 3, 0. Här är de två första villkoren inte är uppfyllda (partiell överlappning). Vi får en mid . Den calling line anger vilken RangeMinimumQuery kallas efter detta uttalande. Vi anger RangeMinimumQuery samtal inom proceduren som respektive 1 och 2. Vår tabell kommer att se ut:
+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 0 | 3 | 0 | 1 | 1 |
+------+-------+-----+------+----------+-----+--------------+
Så när vi kallar RangeMinimumQuery-1 passerar vi: low = 0 , high = mid = 1 , position = 2*position+1 = 1 . En sak du kan märka, det är 2*position+1 är det vänstra barnet i en nod . Det betyder att vi kontrollerar rotens vänstra barn. Eftersom [1,3] delvis överlappar [0,1] , de två första villkoren inte uppfylls, får vi en mid . Vårt bord:
+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 0 | 3 | 0 | 1 | 1 |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 0 | 1 | 1 | 0 | 1 |
+------+-------+-----+------+----------+-----+--------------+
I nästa rekursiva samtal passerar vi low = 0 , high = mid = 0 , position = 2*position+1 = 3 . Vi når vårt vänstra blad. Eftersom [1,3] inte överlappar med [0,0] återgår vi infinity till vår kallande funktion. Rekursionstabell:
+------+-------+-----+------+----------+-----+--------------+
| 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 | | |
+------+-------+-----+------+----------+-----+--------------+
Eftersom detta rekursiva samtal är slutfört, går vi tillbaka till föregående rad i vårt rekursionstabell. Vi får:
+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 0 | 3 | 0 | 1 | 1 |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 0 | 1 | 1 | 0 | 1 |
+------+-------+-----+------+----------+-----+--------------+
I vår procedur utför vi RangeMinimumQuery-2 samtal. Den här gången passerar vi low = mid+1 = 1 , high = 1 och position = 2*position+2 = 4 . Vår calling line changes to **2** . Vi får:
+------+-------+-----+------+----------+-----+--------------+
| 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 | | |
+------+-------+-----+------+----------+-----+--------------+
Så vi går till rätt barn i föregående nod. Den här gången är det en total överlappning. Vi returnerar värdet SegmentTree[position] = SegmentTree[4] = 2 .
+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 0 | 3 | 0 | 1 | 1 |
+------+-------+-----+------+----------+-----+--------------+
Tillbaka vid samtalsfunktionen kontrollerar vi vad som är minimi av de två returnerade värdena för två samtalsfunktioner. Självklart är minimum 2 , vi återgår 2 till den samtalande funktionen. Vår rekursionstabell ser ut som:
+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 0 | 3 | 0 | 1 | 1 |
+------+-------+-----+------+----------+-----+--------------+
Vi är klara att titta på den vänstra delen av vårt segmentträd. Nu kommer vi att ringa RangeMinimumQuery-2 härifrån. Vi passerar low = mid+1 = 1+1 =2 , high = 3 och position = 2*position+2 = 2 . Vårt bord:
+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 0 | 3 | 0 | 1 | 1 |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 2 | 3 | 2 | | |
+------+-------+-----+------+----------+-----+--------------+
Det finns en total överlappning. Så vi returnerar värdet: SegmentTree[position] = SegmentTree[2] = 0 . Vi kommer tillbaka till rekursionen varifrån dessa två barn kallades och får minst (4,0) , det vill säga 0 och returnera värdet.
Efter att ha genomfört proceduren får vi 0 , vilket är det minsta från index- 1 till index- 3 .
Runtime komplexitet för denna procedur är O(logn) där n är antalet element i artiklar arrayen. För att utföra en maximal sökfråga måste vi ersätta raden:
Return min(RangeMinimumQuery(SegmentTree, qLow, qHigh, low, mid, 2*position+1),
RangeMinimumQuery(SegmentTree, qLow, qHigh, mid+1, high, 2*position+2))
med:
Return max(RangeMinimumQuery(SegmentTree, qLow, qHigh, low, mid, 2*position+1),
RangeMinimumQuery(SegmentTree, qLow, qHigh, mid+1, high, 2*position+2))
Lat förökning
Låt oss säga att du redan har skapat ett segmentträd. Du måste uppdatera matrisens värden, detta kommer inte bara att ändra bladnoderna i ditt segmentträd, utan också minsta / högsta i vissa noder. Låt oss titta på detta med ett exempel:
Detta är vårt minsta segmentträd med åtta element. För att ge dig en snabb påminnelse representerar varje noder minimivärdet för det område som nämns bredvid dem. Låt oss säga, vi vill öka värdet på den första artikeln i vår matris med 3 . Hur kan vi göra det? Vi följer hur vi genomförde RMQ. Processen ser ut som:
- Först korsar vi roten. [0,0] överlappar delvis med [0,7] , vi går till båda riktningarna.
- Vid vänster undertråd, [0,0] överlappar delvis med [0,3] , går vi till båda riktningarna.
- Vid vänster undertråd, [0,0] överlappar delvis med [0,1] , går vi till båda riktningarna.
- På vänster underträna överlappar [0,0] totalt [0,0] , och eftersom dess bladnod uppdaterar vi noden genom att öka dess värde med 3 . Och returnera värdet -1 + 3 = 2 .
- Till höger undertråd överlappar [1,1] inte [0,0] , vi returnerar värdet vid noden ( 2 ).
Minsta av dessa två returnerade värden ( 2 , 2 ) är 2 , så vi uppdaterar värdet på den aktuella noden och returnerar det.
- Till höger undertråd [2,3] överlappar inte [0,0] , vi returnerar värdet på noden. ( 1 )
Eftersom det minsta av dessa två returnerade värden ( 2 , 1 ) är 1 , uppdaterar vi värdet på den aktuella noden och returnerar det.
- Vid vänster undertråd, [0,0] överlappar delvis med [0,1] , går vi till båda riktningarna.
- Till höger undertråd [4,7] överlappar inte [0,0] , vi returnerar värdet på noden. ( 1 )
- Vid vänster undertråd, [0,0] överlappar delvis med [0,3] , går vi till båda riktningarna.
- Slutligen uppdateras värdet på rotnoden eftersom minsta antal av de två returnerade värdena (1,1) är 1 .
Vi kan se att uppdatering av en enda nod kräver O(logn) tidskomplexitet, där n är antalet bladnoder. Så om vi blir ombedda att uppdatera några noder från i till j , kommer vi att kräva O(nlogn) tidskomplexitet. Detta blir besvärligt för ett stort värde av n . Låt oss vara lata, dvs. jobba bara när det behövs. Hur? När vi behöver uppdatera ett intervall kommer vi att uppdatera en nod och markera dess barn att det måste uppdateras och uppdatera det vid behov. För detta behöver vi en matris lat av samma storlek som ett segmentträd. Till en början kommer alla element i den lata matrisen att vara 0 som representerar att det inte finns någon väntande uppdatering. Om det finns ett icke-nollelement i lata [i] , måste detta element uppdatera nod i i segmentträdet innan någon fråga görs. Hur ska vi göra det? Låt oss titta på ett exempel:
Låt oss säga, för vårt exempelträd, vill vi utföra några frågor. Dessa är:
- steg [0,3] med 3 .
- steg [0,3] med 1 .
- ökning [0,0] med 2 .
steg [0,3] med 3:
Vi börjar från rotnoden. Först kontrollerar vi om detta värde är uppdaterat. För detta kontrollerar vi vår lata matris som är 0 , det betyder att värdet är aktuellt. [0,3] överlappar delvis [0,7] . Så vi går till båda riktningarna.
- På vänster undertråd finns det ingen väntande uppdatering. [0,3] överlappar totalt [0,3] . Så vi uppdaterar värdet på noden med 3 . Så värdet blir -1 + 3 = 2 . Den här gången kommer vi inte att gå hela vägen. Istället för att gå ner uppdaterar vi motsvarande barn i det lata trädet i vår nuvarande nod och ökar dem med 3 . Vi returnerar också värdet på den aktuella noden.
- På rätt undertråd finns ingen uppdatering i väntan. [0,3] överlappar inte [4,7] . Så vi returnerar värdet på den aktuella noden (1) .
Minst två returnerade värden ( 2 , 1 ) är 1 . Vi uppdaterar rotnoden till 1 .
Vårt segmentträd och lata träd ser ut som:
Värdena utan noll i noderna i vårt Lazy Tree representerar, det finns uppdateringar som väntar på dessa noder och nedan. Vi uppdaterar dem vid behov. Om vi blir frågade, vad är det minsta inom intervallet [0,3] , kommer vi till vänsterundertree i rotnoden och eftersom det inte finns några väntande uppdateringar returnerar vi 2 , vilket är korrekt. Så den här processen påverkar inte riktigheten av vår segmentträdalgoritm.
steg [0,3] med 1:
- Vi börjar från rotnoden. Det finns ingen väntande uppdatering. [0,3] överlappar delvis [0,7] . Så vi går till båda riktningarna.
- I vänster undertråd finns ingen uppdatering i väntan. [0,3] överlappar helt [0,3] . Vi uppdaterar den aktuella noden: 2 + 1 = 3 . Eftersom detta är en intern nod uppdaterar vi dess barn i Lazy Tree för att ökas med 1 . Vi kommer också att returnera värdet på den aktuella noden ( 3 ).
- I rätt undertråd finns ingen uppdatering i väntan. [0,3] överlappar inte [4,7] . Vi returnerar värdet på den aktuella noden ( 1 ).
- Vi uppdaterar rotnoden genom att ta minst två returnerade värden ( 3 , 1 ).
Vårt segmentträd och lata träd kommer att se ut:
Som ni ser samlar vi uppdateringarna på Lazy Tree men skjuter inte ner dem. Detta är vad Lazy propagation betyder. Om vi inte hade använt det, var vi tvungna att pressa värdena ner till bladen, vilket skulle kosta oss mer onödig tidskomplexitet.
ökning [0,0] med 2:
- Vi börjar från rotnoden. Eftersom roten är aktuell och [0,0] överlappar delvis [0,7] , går vi till båda riktningarna.
- I den vänstra undertråden är den aktuella noden uppdaterad och [0,0] överlappar delvis [0,3] , vi går till båda riktningarna.
- I den vänstra undertråden har den nuvarande noden i Lazy Tree ett värde som inte är noll. Så det finns en uppdatering som ännu inte har spridits till denna nod. Vi kommer först att uppdatera denna nod i vårt segmentträd. Så detta blir -1 + 4 = 3 . Då ska vi sprida denna fyra till dess barn i Lazy Tree. Eftersom vi redan har uppdaterat den aktuella noden, kommer vi att ändra värdet på den aktuella noden i Lazy Tree till 0 . Sedan överlappar [0,0] delvis [0,1] , så vi går till båda riktningarna.
- I den vänstra noden måste värdet uppdateras eftersom det finns ett värde som inte är noll i den nuvarande noden för Lazy Tree. Så vi uppdaterar värdet till -1 + 4 = 3 . Eftersom [0,0] helt överlappar [0,0] uppdaterar vi värdet på den aktuella noden till 3 + 2 = 5 . Detta är en bladnod, så vi behöver inte sprida värdet längre. Vi uppdaterar motsvarande nod vid Lazy Tree till 0 eftersom alla värden har spridits fram till denna nod. Vi returnerar värdet på den aktuella noden ( 5 ).
- Vid rätt nod måste värdet uppdateras. Så värdet blir: 4 + 2 = 6 . Eftersom [0,0] inte överlappar [1,1] returnerar vi värdet på den aktuella noden ( 6 ). Vi uppdaterar också värdet i Lazy Tree till 0 . Ingen spridning behövs eftersom detta är en bladnod.
Vi uppdaterar den aktuella noden med minst två returnerade värden ( 5 , 6 ). Vi returnerar värdet på den aktuella noden ( 5 ).
- På rätt undertråd finns det en väntande uppdatering. Vi uppdaterar värdet på noden till 1 + 4 = 5 . Eftersom detta inte är en bladnod, sprider vi värdet till dess barn i vårt Lazy Tree och uppdaterar den nuvarande noden till 0 . Eftersom [0,0] inte överlappar med [2,3] , returnerar vi värdet på vår nuvarande nod ( 5 ).
Vi uppdaterar den aktuella noden med minsta möjliga av returnerade värden ( 5 , 5 ) och returnerar värdet ( 5 ).
- I den vänstra undertråden har den nuvarande noden i Lazy Tree ett värde som inte är noll. Så det finns en uppdatering som ännu inte har spridits till denna nod. Vi kommer först att uppdatera denna nod i vårt segmentträd. Så detta blir -1 + 4 = 3 . Då ska vi sprida denna fyra till dess barn i Lazy Tree. Eftersom vi redan har uppdaterat den aktuella noden, kommer vi att ändra värdet på den aktuella noden i Lazy Tree till 0 . Sedan överlappar [0,0] delvis [0,1] , så vi går till båda riktningarna.
- På rätt undertråd finns ingen uppdatering i väntan och eftersom [0,0] inte överlappar [4,7] returnerar vi värdet på den aktuella noden ( 1 ).
- I den vänstra undertråden är den aktuella noden uppdaterad och [0,0] överlappar delvis [0,3] , vi går till båda riktningarna.
- Vi uppdaterar rotnoden med det minsta av de två returnerade värdena ( 5 , 1 ).
Vårt segmentträd och lat träd kommer att se ut:
Vi kan märka att värdet vid [0,0] , när det behövdes, fick all inkrement.
Om du nu blir ombedd att hitta minsta inom intervallet [3,5] , om du har förstått fram till denna punkt, kan du enkelt ta reda på hur frågan skulle gå och det returnerade värdet blir 1 . Vårt segment Tree and Lazy Tree skulle se ut:
Vi har helt enkelt följt samma process som vi följde när vi hittade RMQ med extra begränsningar för att kontrollera Lazy Tree för väntande uppdateringar.
En annan sak vi kan göra är att istället för att returnera värden från varje nod, eftersom vi vet vad som kommer att vara barnnoden för vår nuvarande nod, kan vi helt enkelt kontrollera dem för att hitta minsta av dessa två.
Pseudokoden för uppdatering i Lazy Propagation skulle vara:
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])
Och pseudokoden för RMQ i Lazy Propagation kommer att vara:
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)