0Pricing
Coding Interview Prep · Lekcja

Leniwa propagacja aktualizacji zakresów

Odroczone aktualizacje całych zakresów

Leniwa propagacja aktualizacji zakresów to bezpłatna lekcja Coding Interview Prep na CoddyKit. To lekcja 4 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Coding Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.

Problem aktualizacji przedziału

Co zrobić, gdy zapytanie nakazuje dodać 5 do każdego elementu od l do r? Odwiedzanie każdego liścia zajmuje O(n) na aktualizację, co przy wielu aktualizacjach przedziałów jest zdecydowanie zbyt wolne. 😰

Pomysł leniwej propagacji

Leniwa propagacja pozwala węzłowi zapamiętać oczekującą zmianę bez przekazywania jej od razu do dzieci. Praca zostaje odroczona do chwili, gdy te dzieci będą rzeczywiście potrzebne.

Druga tablica na oczekujące zmiany

Obok drzewa przechowujemy tablicę lazy. lazy[node] zawiera aktualizację dotyczącą całego przedziału tego węzła, która nie została jeszcze przekazana niżej.

lazy = [0] * (4 * n)

Zastosowanie do całego węzła

Gdy aktualizacja obejmuje cały węzeł, należy zmienić zapisaną wartość i umieścić zmianę w lazy, a następnie zakończyć działanie. Nie ma potrzeby schodzić niżej.

seg[node] += (r - l + 1) * val
lazy[node] += val

Przekazywanie w dół przed zejściem niżej

Przed odwiedzeniem dzieci należy przekazać w dół każdą oczekującą wartość lazy do obojga dzieci. Dzięki temu dzieci są poprawne dokładnie wtedy, gdy są odczytywane.

def push_down(node, l, r):
    if lazy[node]:
        apply(2*node, l, mid)
        apply(2*node+1, mid+1, r)
        lazy[node] = 0

Trzy przypadki dla każdego węzła

Dla każdego węzła zakres zapytania jest rozłączny z jego zakresem, obejmuje go w całości albo obejmuje go częściowo. Odpowiednio należy pominąć węzeł, zastosować aktualizację leniwie lub rekurencyjnie przejść do obu połówek.

Leniwe aktualizacje zachowują złożoność logarytmiczną

Aktualizacja przedziału odwiedza tylko O(log n) węzłów, ponieważ węzły w pełni objęte aktualizacją kończą działanie wcześniej. Na tym polega cała korzyść z leniwej propagacji. ⚡

Zapytania również wymagają propagacji w dół

Zapytania przedziałowe również muszą najpierw propagować zmiany w dół przed wywołaniem rekurencji, aby odczytywać aktualne wartości dzieci. Pominięcie tego kroku to klasyczny błąd leniwej propagacji.

Aktualizuj w górę po rekurencji

Po zaktualizowaniu dzieci scal na ich podstawie węzeł nadrzędny. To uaktualnianie w górę zapewnia spójność każdego węzła wewnętrznego z jego poddrzewem.

seg[node] = seg[2*node] + seg[2*node+1]

Przypisanie a dodawanie

Leniwa propagacja działa z wieloma operacjami, ale przypisanie i dodawanie łączą się inaczej. Zanim napiszesz kod, ustal, jak scalać dwie oczekujące aktualizacje.

Kiedy warto użyć leniwej propagacji

Sięgaj po leniwą propagację tylko wtedy, gdy naprawdę potrzebujesz aktualizacji przedziałowych. Przy samych aktualizacjach punktowych zwykłe drzewo przedziałowe jest prostsze i wystarczające.

Szybkie sprawdzenie

Co musi się wydarzyć przed wywołaniem rekurencji dla dzieci węzła?

Podsumowanie: odroczone aktualizacje

Poznałeś(-aś) leniwą propagację: przechowuj oczekujące zmiany, propaguj je w dół przed zejściem, aktualizuj węzeł w górę po powrocie i uzyskaj aktualizacje przedziałowe w czasie O(log n). 🎉

Często zadawane pytania

Czy lekcja „Leniwa propagacja aktualizacji zakresów” jest bezpłatna?

Tak — pełny tekst „Leniwa propagacja aktualizacji zakresów” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Coding Interview Prep, przejdź na CoddyKit PRO. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.

Co nauczysz się w „Leniwa propagacja aktualizacji zakresów”?

Odroczone aktualizacje całych zakresów Ćwiczysz Coding Interview Prep z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.

Czy potrzebuję doświadczenia, aby zacząć Coding Interview Prep?

Nie wymagamy żadnego doświadczenia. Coding Interview Prep w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 4 z 4.

Ile czasu zajmuje lekcja „Leniwa propagacja aktualizacji zakresów”?

Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.

Czy mogę pisać i uruchamiać kod w tej lekcji Coding Interview Prep?

Tak. Każda lekcja Coding Interview Prep zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.

Wszystkie lekcje w tym kursie

  1. Drzewo Fenwicka dla sum prefiksowych
  2. Inwersje z BIT
  3. Drzewo przedziałowe: budowanie i zapytania
  4. Leniwa propagacja aktualizacji zakresów
← Powrót do Coding Interview Prep