Drzewo przedziałowe: budowanie i zapytania
Minimum, maksimum lub suma zakresu w log n
Drzewo przedziałowe: budowanie i zapytania to bezpłatna lekcja Competitive Programming Academy na CoddyKit. To lekcja 3 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 Competitive Programming Academy, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Competitive Programming Academy zawiera 4 lekcji w sumie.
Co dalej po drzewie Fenwicka
Drzewo Fenwicka świetnie sprawdza się dla sum, ale drzewo przedziałowe obsługuje wartości minimalne, maksymalne, NWD i wiele innych operacji. Jest elastycznym narzędziem do zapytań o przedziały.
Drzewo nad przedziałami
Każdy węzeł odpowiada za pewien przedział tablicy. Korzeń obejmuje całość, a dzieci dzielą przedział na połowy, aż liście będą przechowywać pojedyncze elementy.
Przechowywanie w tablicy
Drzewo przechowujemy w płaskiej tablicy o rozmiarze 2n lub 4n. Węzeł 1 jest korzeniem, a dzieci węzła i znajdują się pod indeksami 2i i 2i+1.
seg = [0] * (2 * n)Dane znajdują się w liściach
W wersji iteracyjnej wartości początkowe znajdują się w drugiej połowie tablicy, pod indeksami od n do 2n-1.
for i in range(n):
seg[n + i] = a[i]Budowanie od dołu
Każdy węzeł wewnętrzny powstaje przez operację combine na jego dwojgu dzieciach. Należy wypełniać węzły od n-1 do 1, a całe drzewo będzie gotowe.
for i in range(n - 1, 0, -1):
seg[i] = seg[2*i] + seg[2*i+1]Operacja combine
Funkcja combine definiuje działanie drzewa. Dla sum należy użyć dodawania, dla minimów — min, a dla maksimów — max. Wystarczy ją zamienić, aby zmienić rodzaj zapytania.
def combine(x, y):
return min(x, y)Aktualizacja punktowa i przejście w górę
Aby zmienić jedną wartość, należy ustawić liść i przejść do korzenia, po drodze przeliczając każdego rodzica na podstawie jego dwojga dzieci.
i += n
seg[i] = value
while i > 1:
i //= 2
seg[i] = combine(seg[2*i], seg[2*i+1])Zapytanie o przedział półotwarty
Zapytania o przedział przeglądają elementy z obu końców, włączając w wynik węzły brzegowe. Przedział jest półotwarty i obejmuje l, ale nie obejmuje r.
Iteracyjna pętla zapytania
Należy przesuwać l i r ku sobie. Gdy indeks jest nieparzystą granicą, trzeba uwzględnić ten węzeł przed przesunięciem wskaźnika.
while l < r:
if l & 1: res = combine(res, seg[l]); l += 1
if r & 1: r -= 1; res = combine(res, seg[r])
l //= 2; r //= 2Złożoność logarytmiczna z obu stron
Budowanie ma złożoność O(n), a każda aktualizacja i każde zapytanie — O(log n). To połączenie sprawia, że drzewa przedziałowe są tak wszechstronne.
Pamiętaj o elemencie neutralnym
Wynik należy rozpocząć od elementu neutralnego danej operacji: od 0 dla sumy, nieskończoności dla minimum lub ujemnej nieskończoności dla maksimum. Nieprawidłowa wartość początkowa prowadzi do błędnych wyników.
res = float('inf')Szybki test
Gdzie w drzewie iteracyjnym znajdują się surowe dane?
Podsumowanie: elastyczne przedziały
Zbudował(a) Pan/Pani drzewo przedziałowe: z liśćmi w drugiej połowie tablicy i rodzicami tworzonymi przez operację combine, z aktualizacjami i zapytaniami o sumę, minimum lub maksimum w czasie O(log n). 🌳
Często zadawane pytania
Czy lekcja „Drzewo przedziałowe: budowanie i zapytania” jest bezpłatna?
Tak — pełny tekst „Drzewo przedziałowe: budowanie i zapytania” 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 Competitive Programming Academy, przejdź na CoddyKit PRO. Kurs Competitive Programming Academy zawiera 4 lekcji w sumie.
Co nauczysz się w „Drzewo przedziałowe: budowanie i zapytania”?
Minimum, maksimum lub suma zakresu w log n Ćwiczysz Competitive Programming Academy 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ąć Competitive Programming Academy?
Nie wymagamy żadnego doświadczenia. Competitive Programming Academy 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 3 z 4.
Ile czasu zajmuje lekcja „Drzewo przedziałowe: budowanie i zapytania”?
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 Competitive Programming Academy?
Tak. Każda lekcja Competitive Programming Academy 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