Struktury danych/Drzewa/Drzewa przedziałowe

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[0] - maksimum całego drzewa
  • max[1] - maksimum elementów 0...${\frac {n}{2}}-1$
  • max[2] - maksimum elementów ${\frac {n}{2}}$...$n$
  • max[3] - maksimum elementów 0...${\frac {n}{4}}-1$
  • max[4] - maksimum elementów ${\frac {n}{4}}$...${\frac {n}{2}}-1$
  • max[5] - maksimum elementów ${\frac {n}{2}}$...${\frac {3n}{4}}-1$
  • max[6] - maksimum elementów ${\frac {3n}{4}}$...$n$
  • 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]: 0...31

tab[1]: 0..15

tab[2]: 16..31

tab[3]: 0..7

tab[4]: 8..15

tab[5]: 16..23

tab[6]: 24..31

tab[7]: 0..3

tab[8]: 4..7

tab[9]: 8..11

tab[10]: 12..15

tab[11]: 16..19

tab[12]: 20..23

tab[13]: 24..27

tab[14]: 28..31

tab[15]: 0..1

tab[16]: 2..3

tab[17]: 4..5

tab[18]: 6..7

tab[19]: 8..9

tab[20]: 10..11

tab[21]: 12..13

tab[22]: 14..15

tab[23]: 16..17

tab[24]: 18..19

tab[25]: 20..21

tab[26]: 22..23

tab[27]: 24..25

tab[28]: 26..27

tab[29]: 28..29

tab[30]: 30..31

Ustawianie wartości elementu

Algorytm jest następujący:

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

1. Ustawiamy i: identyfikator bieżącego zakresu na 0
2. Ustawiamy sumę p_sum na 0
3. 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
4. //wiemy, że n odpowiada przedziałowi na samym dole
5. k=k-p_sum
6. Ustawiamy val[l]=k
7. Ustawiamy i na bezpośredniego ojca elementu l
8. 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.
9. 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.

1. Ustawiamy i: identyfikator bieżącego zakresu na 0
2. Ustawiamy sumę p_sum na 0
3. 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
4. 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]