Lat propagation för intervalluppdateringar
Skjut upp uppdateringar över hela intervall
Lat propagation för intervalluppdateringar är en gratis lektion i Förberedelse inför kodningsintervjuer på CoddyKit. Detta är lektion 4 av 4. Ni kan läsa hela lektionen gratis nedan och sedan öva praktiskt i webbläsaren med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt. Den ingår i lärvägen för Förberedelse inför kodningsintervjuer, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i Förberedelse inför kodningsintervjuer innehåller totalt 4 lektioner.
Problemet med intervalluppdateringar
Vad händer om en fråga säger att 5 ska läggas till varje element från l till r? Att beröra varje löv tar O(n) per uppdatering, vilket är alldeles för långsamt vid många intervalluppdateringar. 😰
Den lata idén
Lazy propagation låter en nod komma ihåg en väntande ändring utan att skicka den vidare till barnen ännu. Arbetet skjuts upp tills ni faktiskt behöver dessa barn.
En andra array för väntande arbete
Vid sidan av trädet behåller vi en lazy-array. lazy[node] lagrar en uppdatering som gäller för hela nodens intervall men ännu inte har skickats nedåt.
lazy = [0] * (4 * n)Tillämpa på en hel nod
När en uppdatering täcker en nod helt justerar ni dess lagrade värde och lägger ändringen i lazy, och avslutar sedan. Det finns ingen anledning att gå djupare.
seg[node] += (r - l + 1) * val
lazy[node] += valSkicka nedåt innan ni går djupare
Innan ni besöker barnen ska ni skicka nedåt alla väntande lazy-värden till dem båda. Då är barnen korrekta precis när ni läser dem.
def push_down(node, l, r):
if lazy[node]:
apply(2*node, l, mid)
apply(2*node+1, mid+1, r)
lazy[node] = 0Tre fall per nod
Vid varje nod är frågeintervallet disjunkta, helt täckande eller partiellt täckande. Hoppa över, tillämpa lazy eller gå rekursivt in i båda halvorna.
Lazy-uppdateringar förblir logaritmiska
En intervalluppdatering berör bara O(log n) noder eftersom noder som täcks helt avslutas tidigt. Det är hela vinsten med att använda lazy propagation. ⚡
Även frågor måste propagera nedåt
Intervallfrågor måste också propagera nedåt före rekursionen, så att de läser aktuella värden från barnnoderna. Att glömma detta är det klassiska felet vid lazy propagation.
Sammanfoga efter rekursion
Efter att barnen har uppdaterats ska du slå ihop föräldern utifrån dem. Denna sammanfogning uppåt håller varje intern nod konsekvent med sitt delträd.
seg[node] = seg[2*node] + seg[2*node+1]Tilldelning kontra addition
Lazy propagation fungerar för många operationer, men tilldelning och addition kombineras på olika sätt. Bestäm hur två väntande uppdateringar ska slås ihop innan du implementerar detta.
När lazy propagation är värt det
Använd lazy propagation endast när du verkligen behöver intervalluppdateringar. För enbart punktuppdateringar är ett vanligt segmentträd enklare och tillräckligt.
Snabb kontroll
Vad måste ske innan du går vidare rekursivt till en nods barn?
Sammanfattning: Fördröjda uppdateringar
Du har lärt dig lazy propagation: lagra väntande ändringar, propagera nedåt innan du går djupare, sammanfoga uppåt efteråt och få intervalluppdateringar i O(log n). 🎉
Lär dig Förberedelse inför kodningsintervjuer med en AI-lärare – gratis
Skriv och kör riktig kod i webbläsaren, få omedelbar hjälp av en AI-lärare dygnet runt och fortsätt där du slutade – på webben eller i appen.
- Kurser
- 90
- Lektioner
- 360
Vanliga frågor
Är lektionen ”Lat propagation för intervalluppdateringar” gratis?
Ja – hela texten till ”Lat propagation för intervalluppdateringar” kan läsas gratis här på webben. Om Ni vill öva interaktivt med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt och låsa upp resten av kursen i Förberedelse inför kodningsintervjuer, kan Ni uppgradera till CoddyKit PRO. Kursen i Förberedelse inför kodningsintervjuer innehåller totalt 4 lektioner.
Vad lär jag mig i ”Lat propagation för intervalluppdateringar”?
Skjut upp uppdateringar över hela intervall Ni övar på Förberedelse inför kodningsintervjuer med praktisk kod som körs direkt i webbläsaren, medan en AI-handledare som är tillgänglig dygnet runt svarar på Era frågor under lektionen.
Behöver jag någon erfarenhet för att börja lära mig Förberedelse inför kodningsintervjuer?
Du behöver inga förkunskaper. Utbildningen i Förberedelse inför kodningsintervjuer på CoddyKit är upplagd för allt från nybörjare till avancerade elever, så att du kan börja här eller från början och gå fram i din egen takt. Detta är lektion 4 av 4.
Hur lång tid tar lektionen ”Lat propagation för intervalluppdateringar”?
De flesta CoddyKit-lektioner tar cirka 5–10 minuter. Varje lektion är kort och interaktiv, så att du gör stadiga framsteg och kan fortsätta precis där du slutade – på webben eller i appen.
Kan jag skriva och köra kod i den här Förberedelse inför kodningsintervjuer-lektionen?
Ja. Varje Förberedelse inför kodningsintervjuer-lektion innehåller en inbyggd kodredigerare, så att du kan skriva och köra riktig kod direkt i webbläsaren och få omedelbar AI-feedback – utan lokal installation.
Alla lektioner i den här kursen
- Fenwick-träd för prefixsummor
- Inversioner med ett BIT
- Segmentträd: bygg och fråga
- Lat propagation för intervalluppdateringar