Lazy propagation voor bereikupdates
Updates over volledige bereiken uitstellen
Lazy propagation voor bereikupdates is een gratis Voorbereiding op programmeerinterviews-les op CoddyKit. Dit is les 4 van 4. Je kunt de volledige les hieronder gratis lezen en daarna in de browser praktisch oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is. Deze les maakt deel uit van het leertraject Voorbereiding op programmeerinterviews. Je voortgang wordt gesynchroniseerd op het web en in de CoddyKit-app. De cursus Voorbereiding op programmeerinterviews bevat in totaal 4 lessen.
Het probleem van bereiksupdates
Wat als een vraag zegt dat je 5 moet optellen bij elk element van l tot r? Elk blad aanraken kost O(n) per update, veel te traag bij veel bereiksupdates. 😰
Het luie idee
Luie propagatie laat een knoop een uitgestelde verandering onthouden zonder die al naar de kinderen door te geven. Het werk wordt uitgesteld totdat je die kinderen echt nodig hebt.
Een tweede array voor uitgesteld werk
Naast de boom houden we een lazy-array bij. lazy[node] bevat een update die op het volledige bereik van die knoop van toepassing is, maar nog niet naar beneden is doorgegeven.
lazy = [0] * (4 * n)Toepassen op een volledige knoop
Wanneer een update een knoop volledig omvat, pas je de opgeslagen waarde aan en stapel je de verandering op in lazy. Daarna stop je. Afdalen is niet nodig.
seg[node] += (r - l + 1) * val
lazy[node] += valGeef door voordat je afdaalt
Geef vóór het bezoeken van de kinderen elke uitgestelde lazy-waarde naar beneden door aan beide kinderen. Zo zijn de kinderen precies correct wanneer je ze uitleest.
def push_down(node, l, r):
if lazy[node]:
apply(2*node, l, mid)
apply(2*node+1, mid+1, r)
lazy[node] = 0Drie gevallen per knoop
Bij elke knoop is het vraagbereik disjunct, volledig omvattend of gedeeltelijk overlappend. Sla over, pas lui toe of ga recursief door in beide helften.
Luie updates blijven logaritmisch
Een bereikupdate raakt slechts O(log n) knopen, omdat knopen die volledig worden omvat vroeg stoppen. Dat is het volledige voordeel van lui werken. ⚡
Query's ook naar beneden doorgeven
Bereikquery's moeten vóór de recursie ook naar beneden worden doorgegeven, zodat ze de actuele waarden van kinderen lezen. Dit vergeten is de klassieke fout bij lazy propagation.
Omhoog samenvoegen na recursie
Na het bijwerken van de kinderen voeg je de ouder opnieuw samen op basis van die kinderen. Door dit omhoog doorgeven blijft elke interne knoop consistent met zijn deelboom.
seg[node] = seg[2*node] + seg[2*node+1]Toewijzing versus optelling
Lazy propagation werkt voor veel bewerkingen, maar toewijzing en optelling worden anders gecombineerd. Bepaal hoe twee uitstaande updates worden samengevoegd voordat je de code schrijft.
Wanneer lazy propagation de moeite waard is
Gebruik lazy propagation alleen als je echt bereikupdates nodig hebt. Voor alleen puntsgewijze updates is een gewone segmentboom eenvoudiger en voldoende.
Snelle controle
Wat moet er gebeuren voordat je recursief de kinderen van een knoop bezoekt?
Herhaling: uitgestelde updates
Je hebt lazy propagation geleerd: sla uitgestelde wijzigingen op, geef ze door naar beneden voordat je afdaalt, voeg daarna omhoog samen en krijg bereikupdates in O(log n). 🎉
Leer Voorbereiding op programmeerinterviews met een AI-tutor — gratis
Schrijf echte code en voer die uit in je browser, krijg direct hulp van een AI-tutor die 24/7 beschikbaar is en ga verder waar je gebleven bent op het web of in de app.
- Cursussen
- 90
- Lessen
- 360
Veelgestelde vragen
Is de les “Lazy propagation voor bereikupdates” gratis?
Ja — de volledige tekst van “Lazy propagation voor bereikupdates” kun je hier gratis op het web lezen. Als je interactief wilt oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is, en de rest van de cursus Voorbereiding op programmeerinterviews wilt ontgrendelen, kun je upgraden naar CoddyKit PRO. De cursus Voorbereiding op programmeerinterviews bevat in totaal 4 lessen.
Wat leer ik in “Lazy propagation voor bereikupdates”?
Updates over volledige bereiken uitstellen Je oefent met Voorbereiding op programmeerinterviews door code rechtstreeks in de browser uit te voeren. Een AI-begeleider die 24/7 beschikbaar is beantwoordt je vragen terwijl je de les doorwerkt.
Heb ik ervaring nodig om met Voorbereiding op programmeerinterviews te beginnen?
Ervaring vooraf is niet nodig. Voorbereiding op programmeerinterviews op CoddyKit is opgebouwd voor beginners tot gevorderden, zodat je hier of bij het begin kunt starten en in je eigen tempo kunt leren. Dit is les 4 van 4.
Hoe lang duurt de les “Lazy propagation voor bereikupdates”?
De meeste lessen van CoddyKit duren ongeveer 5–10 minuten. Elke les is kort en interactief, zodat je gestaag vooruitgaat en op het web en in de app precies verdergaat waar je was gebleven.
Kan ik code schrijven en uitvoeren in deze les over Voorbereiding op programmeerinterviews?
Ja. Elke les over Voorbereiding op programmeerinterviews bevat een ingebouwde code-editor, zodat je rechtstreeks in je browser echte code kunt schrijven en uitvoeren en direct feedback van AI krijgt — lokale installatie is niet nodig.
Alle lessen in deze cursus
- Fenwick Tree voor prefixsommen
- Inversies met een BIT
- Segment Tree: bouwen en query's uitvoeren
- Lazy propagation voor bereikupdates