← 🤖 Algorytmy i AI
📏 Drzewo przedziałowe
Zapytania na przedziale w czasie O(log n)
Tryb
Zapytanie [L, R]
Aktualizacja punktowa
Statystyki
Rozmiar tablicy
0
Odwiedzone węzły
0
Wynik zapytania
—
Tryb
Suma
Informacje i teoria

Drzewo przedziałowe to drzewo binarne zbudowane nad indeksami tablicy, w którym każdy węzeł pokrywa spójny przedział. Liście pokrywają pojedyncze elementy; każdy węzeł wewnętrzny przechowuje agregat (sumę lub minimum) swojego przedziału, obliczony z dwóch jego węzłów potomnych.

Budowa w czasie O(n)

Budowa od dołu do góry (lub przez rekurencyjny podział metodą „dziel i zwyciężaj”) łączy n liści w ~2n węzłów łącznie, wykonując O(1) pracy na węzeł — czyli O(n) łącznie.

Zapytanie na przedziale w czasie O(log n)

Zapytanie [L,R] rekurencyjnie schodzi w przedział węzła: jeśli leży on całkowicie poza [L,R] — pomijamy; jeśli leży całkowicie wewnątrz — używamy bezpośrednio wcześniej obliczonego agregatu węzła; jeśli częściowo się pokrywa — schodzimy rekurencyjnie do obu węzłów potomnych. Łącznie łączy się co najwyżej O(log n) węzłów, ponieważ przedział zapytania rozkłada się co najwyżej na dwa „łańcuszki” kanonicznych podprzedziałów na każdym poziomie drzewa.

Aktualizacja punktowa w czasie O(log n)

Aktualizacja jednego elementu tablicy unieważnia jedynie O(log n) przodków na ścieżce od tego liścia do korzenia; każdy z nich jest przeliczany na podstawie dwóch swoich węzłów potomnych w drodze powrotnej.

Dlaczego nie po prostu sumy prefiksowe?

Sumy prefiksowe odpowiadają na zapytanie o sumę na przedziale w czasie O(1), ale wymagają O(n) do aktualizacji jednego elementu i w ogóle nie obsługują zapytania o minimum na przedziale (minimum nie ma operacji odwrotnej). Drzewo przedziałowe zamienia niewielką część szybkości zapytania na szybkie aktualizacje i obsługę dowolnego operatora łącznego.

Poza tą symulacją

Leniwa propagacja rozszerza drzewa przedziałowe, aby obsługiwać aktualizacje w czasie O(log n) na całym przedziale (a nie tylko punktowe aktualizacje), odkładając niezastosowane aktualizacje poddrzew, dopóki naprawdę nie zostaną odwiedzone.

O tej symulacji

Autor: Zespół MySimulator · Weryfikacja redakcyjna: Redakcja MySimulator

Zaktualizowano: 11 lipca 2026 r.

Drzewo przedziałowe to drzewo binarne zbudowane nad indeksami tablicy, w którym każdy węzeł reprezentuje spójny przedział i przechowuje wartość zagregowaną — sumę, minimum, maksimum lub dowolną inną kombinację łączną — tego przedziału, obliczoną z jego dwóch węzłów potomnych. Budowa zajmuje O(n) czasu i mniej więcej od 2n do 4n węzłów dla tablicy z n elementami. Zapytanie na przedziale [L, R] rekurencyjnie schodzi przez drzewo, od razu korzystając z wcześniej obliczonego agregatu węzła, gdy jego przedział leży całkowicie wewnątrz [L, R], pomijając przedziały leżące całkowicie poza nim i schodząc do węzłów potomnych tylko w przypadku częściowego pokrycia; dotyczy to co najwyżej O(log n) węzłów, ponieważ zapytanie rozkłada się na ograniczoną liczbę kanonicznych podprzedziałów na każdym poziomie. Aktualizacja punktowa wymaga przeliczenia jedynie O(log n) przodków na ścieżce od zmienionego liścia do korzenia. W porównaniu z sumami prefiksowymi, które odpowiadają na zapytanie o sumę w czasie O(1), ale wymagają O(n) do aktualizacji elementu i w ogóle nie obsługują zapytania o minimum na przedziale, drzewo przedziałowe zamienia niewielki stały koszt zapytania na aktualizacje w czasie O(log n) oraz obsługę dowolnego operatora łącznego.

🔬 Co pokazuje

Symulacja buduje drzewo przedziałowe nad tablicą dziesięciu elementów i wizualizuje, które węzły biorą udział w każdej operacji. Węzły liściowe (na dole drzewa) odpowiadają pojedynczym elementom tablicy; każdy węzeł wewnętrzny powyżej pokazuje agregat (sumę lub minimum) swojego przedziału. Podczas zapytania podświetlane są dokładnie te węzły, których przedziały w pełni pokrywają [L, R] — i jest ich zawsze co najwyżej O(log n), niezależnie od rozmiaru przedziału zapytania.

🎮 Jak korzystać

Wybierz tryb „Suma” lub „Minimum”, ustaw przedział [L, R] i kliknij „Zapytanie”, aby zobaczyć, które węzły są łączone i jaki wynik zostaje uzyskany. Wpisz indeks i nową wartość, a następnie kliknij „Aktualizacja punktowa”, aby zmienić jeden element tablicy i zobaczyć, jak aktualizacja wędruje ścieżką przodków aż do korzenia. Przycisk „Losuj tablicę” generuje nową losową tablicę i buduje drzewo od nowa.

💡 Czy wiesz, że…

Drzewo przedziałowe z n elementami wykorzystuje mniej więcej 2n–4n węzłów, czyli tylko stały narzut w porównaniu z tablicą wejściową — a w zamian otrzymuje zapytania i aktualizacje w czasie O(log n) zamiast O(n). Rozszerzenia takie jak leniwa propagacja idą jeszcze dalej, umożliwiając aktualizację całego przedziału w czasie O(log n), a nie tylko jednego elementu.

Najczęściej zadawane pytania

Dlaczego zapytanie do drzewa przedziałowego dotyka jedynie O(log n) węzłów?

Dowolny przedział zapytania [L, R] można rozłożyć na co najwyżej O(log n) „kanonicznych” przedziałów węzłów — na każdym poziomie rekurencji granica zapytania może podzielić co najwyżej dwa węzły na częściowe pokrycia, podczas gdy wszystko, co leży ściśle między tymi granicami, jest albo w pełni uwzględnione, albo w pełni wykluczone. Zsumowanie tej ograniczonej pracy na wszystkich O(log n) poziomach drzewa daje łączny koszt zapytania O(log n).

Dlaczego stosować drzewo przedziałowe zamiast sum prefiksowych do zapytań na przedziale?

Sumy prefiksowe odpowiadają na zapytanie o sumę na przedziale w czasie O(1), ale wymagają O(n) pracy do aktualizacji jednego elementu tablicy, ponieważ każda suma prefiksowa po tym indeksie musi się przesunąć. Sumy prefiksowe w ogóle nie mogą też odpowiadać na zapytania o minimum na przedziale, ponieważ odejmowanie nie ma odpowiednika dla minimum. Drzewo przedziałowe obsługuje zarówno punktowe aktualizacje, jak i zapytania na przedziale — dla dowolnego operatora łącznego — w czasie O(log n).

Jak aktualizacja punktowa rozchodzi się przez drzewo?

Aktualizacja tablicy pod jednym indeksem zmienia dokładnie jeden liść. Następnie aktualizacja wędruje unikalną ścieżką od tego liścia do korzenia, przeliczając agregat każdego przodka jako kombinację bieżących wartości jego dwóch węzłów potomnych. Ponieważ wysokość drzewa wynosi O(log n), dotyczy to łącznie O(log n) węzłów.

Ile pamięci zużywa drzewo przedziałowe?

Rekurencyjne lub oparte na tablicy drzewo przedziałowe nad n elementami zwykle zużywa od 2n do 4n węzłów, w zależności od implementacji (powszechna reprezentacja oparta na tablicy alokuje 4n slotów, aby bezpiecznie obsłużyć rozmiary niebędące potęgą dwójki bez starannego indeksowania). To stały narzut w porównaniu z tablicą wejściową o rozmiarze O(n) — niewielka cena za zapytania i aktualizacje w czasie O(log n).