Drzewo przedziałowe jest strukturą danych umożliwiającą szybkie wykonywanie następujących operacji:

Sprawdzenie wartości elementu (w czasie O(log n)) Zmianę wartości elementu (w czasie O(log n)) Znalezienie maksimum i minimum w przedziale (w czasie O(log n)) Zwiększenie wszystkich elementów w przedziale o pewną wartość (w czasie O(log n))

Implementacja drzewa przedziałowego jest stosunkowo prosta.

Budowa struktury Będę zakładał, że rozmiar drzewa jest całkowitą potęgą dwójki.

Drzewo przedziałowe składa się z czterech tablic:

Tablicy max[0..n-2] - tablicy zawierającej maksimum w danym przedziale: max - maksimum całego drzewa max - maksimum elementów 0... max - maksimum elementów ... max - maksimum elementów 0... max - maksimum elementów ... max - maksimum elementów ... max - maksimum elementów ... i tak dalej, aż do elementów zawierających maksima z par.

Tablicy min[0..n-2], zbudowanej analogicznie, zawierającej minima z zakresów. Tablicy p[0..n-2], zbudowanej analogicznie, zawierającej wartości dodane do każdej liczby z zakresu. Tablicy val[0..n-1], zawierającej wartości elementów.

Elementy tablic min[i] i max[i] (dla 0<=i<n-1) zawierają wartości powiększone o wartości p[] wszystkich synów i oraz o wartość p[i] (warto na to zwrócić uwagę, gdyż może to spowodować trudne do wykrycia błędy).

Budowę tablic max, min oraz p ilustruje tabela, narysowana tutaj dla n==32:

tab: 0...31 tab: 0..15 tab: 16..31 tab: 0..7 tab: 8..15 tab: 16..23 tab: 24..31 tab: 0..3 tab: 4..7 tab: 8..11 tab: 12..15 tab: 16..19 tab: 20..23 tab: 24..27 tab: 28..31 tab: 0..1 tab: 2..3 tab: 4..5 tab: 6..7 tab: 8..9 tab: 10..11 tab: 12..13 tab: 14..15 tab: 16..17 tab: 18..19 tab: 20..21 tab: 22..23 tab: 24..25 tab: 26..27 tab: 28..29 tab: 30..31

Ustawianie wartości elementu

Algorytm jest następujący:

Zakładamy, że mamy do wstawienia element k na pozycję l.

Ustawiamy i: identyfikator bieżącego zakresu na 0 Ustawiamy sumę p_sum na 0 Dodajemy p_sum=p_sum+p[i]. Jeżeli element jest w lewej połowie zakresu, ustawiamy i=i*2+1 i przechodzimy do kroku 3. Jeżeli w prawej: i=i*2+2 i przechodzimy do kroku 3 //wiemy, że n odpowiada przedziałowi na samym dole k=k-p_sum Ustawiamy val[l]=k Ustawiamy i na bezpośredniego ojca elementu l Zwiększamy k o wartość p[i] i porównujemy ją z wartościami min[i] i max[i], w razie potrzeby je aktualizując. Jeżeli i jest równe zeru, kończymy. W przeciwnym wypadku i=(i-1)/2 i przechodzimy do kroku 8

Sprawdzenie wartości elementu

Jak wyżej, l jest pozycją elementu.

Ustawiamy i: identyfikator bieżącego zakresu na 0 Ustawiamy sumę p_sum na 0 Dodajemy p_sum=p_sum+p[i]. Jeżeli element jest w lewej połowie zakresu, ustawiamy i=i*2+1 i przechodzimy do kroku 3. Jeżeli w prawej: i=i*2+2 i przechodzimy do kroku 3 Zwracamy p_sum+tab[l];

Ogólna metoda dla sprawdzenia minimów/maksimów i zwiększania zakresu [TODO]

Sprawdzenie minimum zakresu [TODO] Sprawdzenie maksimum zakresu [TODO]