Drzewo Fenwicka dla sum prefiksowych
Aktualizacja punktu i zapytanie prefiksowe w log n
Drzewo Fenwicka dla sum prefiksowych to bezpłatna lekcja Coding Interview Prep na CoddyKit. To lekcja 1 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.
Dlaczego tablice prefiksowe zawodzą
Zwykła tablica sum prefiksowych natychmiast odpowiada na zapytania o przedziały, ale pojedyncza aktualizacja wymusza jej przebudowanie. Przy wielu aktualizacjach staje się to powolne. ⏱️
Wprowadzenie drzewa Fenwicka
Drzewo Fenwicka, nazywane też BIT, obsługuje zarówno aktualizacje pojedynczych elementów, jak i zapytania o prefiksy w czasie O(log n). Jest podstawowym narzędziem do dynamicznego obliczania sum narastających.
Indeksowanie od jedynki
Drzewo Fenwicka działa na tablicy indeksowanej od 1. Indeksu 0 używamy jako nieużywanego wartownika, dlatego wszystkie rzeczywiste dane zaczynają się na pozycji 1.
tree = [0] * (n + 1)Magia najmłodszego ustawionego bitu
Każdy indeks obejmuje blok wartości. Rozmiar tego bloku jest równy i & -i, czyli wartości najmłodszego ustawionego bitu liczby i. Ten jeden mechanizm napędza całe drzewo.
lowbit = i & -iAktualizacja pojedynczej pozycji
Aby dodać wartość na pozycji i, należy w każdym kroku przesuwać się do przodu o wartość lowbit, odwiedzając każdy blok zawierający i.
while i <= n:
tree[i] += delta
i += i & -iZapytanie o sumę prefiksową
Aby zsumować pierwszych i wartości, należy cofać się w tablicy i w każdym kroku odejmować lowbit, aż do osiągnięcia zera.
s = 0
while i > 0:
s += tree[i]
i -= i & -iObie pętle mają złożoność logarytmiczną
W każdej iteracji pętla usuwa jeden bit, więc wykonuje się najwyżej log n razy. Dzięki temu zarówno aktualizacja, jak i zapytanie pozostają szybkie.
Suma przedziału z dwóch prefiksów
Potrzebna jest suma od l do r? Proszę obliczyć prefix(r) minus prefix(l-1), tak jak w statycznej tablicy prefiksowej, ale tym razem aktualizacje są również tanie.
range_sum = query(r) - query(l - 1)Budowanie drzewa
Najprostsze budowanie polega na wywołaniu update dla każdej wartości początkowej. Daje to O(n log n) i w zupełności wystarcza w większości zadań konkursowych.
for i, v in enumerate(a, 1):
update(i, v)Niewielkie zapotrzebowanie na pamięć
Drzewo Fenwicka potrzebuje tylko jednej tablicy o rozmiarze n+1. To niewielkie zapotrzebowanie na pamięć jest jednym z powodów jego popularności w zadaniach konkursowych. 💾
Kiedy wybrać BIT
Drzewo Fenwicka warto wybrać, gdy aktualizacje pojedynczych elementów przeplatają się z zapytaniami o sumy prefiksowe lub sumy przedziałów. Jest krótkie w implementacji i trudno znaleźć lepsze rozwiązanie.
Szybki test
Proszę utrwalić sposób poruszania się obu pętli.
Podsumowanie: podstawy BIT
Poznał(a) Pan/Pani drzewo Fenwicka: indeksowane od 1, oparte na i & -i, z aktualizacją pojedynczego elementu i zapytaniem o prefiks, które mają złożoność O(log n). Następnie wykorzystamy je do zliczania inwersji. 🎯
Ucz się Coding Interview Prep dzięki korepetycjom AI — za darmo
Pisz i uruchamiaj kod w przeglądarce, otrzymuj natychmiastową pomoc od korepetytora AI dostępnego 24/7 i kontynuuj naukę w sieci lub w aplikacji.
- Kursy
- 90
- Lekcje
- 360
Często zadawane pytania
Czy lekcja „Drzewo Fenwicka dla sum prefiksowych” jest bezpłatna?
Tak — pełny tekst „Drzewo Fenwicka dla sum prefiksowych” 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 „Drzewo Fenwicka dla sum prefiksowych”?
Aktualizacja punktu i zapytanie prefiksowe w log n Ć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 1 z 4.
Ile czasu zajmuje lekcja „Drzewo Fenwicka dla sum prefiksowych”?
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
- Drzewo Fenwicka dla sum prefiksowych
- Inwersje z BIT
- Drzewo przedziałowe: budowanie i zapytania
- Leniwa propagacja aktualizacji zakresów