Drzewo przedziałowe

Punkt-przedział (ppr)

Do czego służy?

Drzewo punkt-przedział to struktura służąca do odczytywania wartości z danych przedziałów a także aktualizacji wartości w danym ciągu. Dla przykładu, dla danego ciągu chcemy w szybkim czasie móc:
1. Odczytać sumę na danym przedziale
2. Zmienić wartość w ciągu
Drzewo punkt-przedział dla tego typu operacji będzie wykonywało log₂(n) operacji, gdzie n to długość ciągu. Zauważmy że przy brutalnym rozwiązaniu, czyli po prostu trzymaniu tablicy z wartościami i za każdym razem liczeniu sumy od nowa złożoność byłaby taka:
-odczytanie sumy - O(n)
-zaaktualizowanie wartości - O(1)
Widzimy więc, że takie rozwiązanie nie wystarcza..... Dlatego jest coś takiego jak drzewo przedziałowe!

Algorytm

Na początku tworzymy drzewo binarne, gdzie wierzchołek nr 1 jest korzeniem. Poszczególne wierzchołki będą odpowiadać za poszczególne przedziały w taki sposób:
Na najniższych poziomach wierzchołki odpowiadają za jedną wartość w ciągu, a każdy wyższy wierzchołek odpowiada za połączone przedziały synów. Tak zbudowane drzewo umożliwia nam w szybkim czasie wykonanie operacji:
Aktualizacji - zaczynamy w dolnym wierzchołku, które odpowiada za aktualizowany punkt. Aktualizujemy go. Następnie przechodzimy do jego ojca, w którym wartość ustawiamy na sumę z synów (jeśli mamy drzewo sumy). Powtarzamy to, dopóki nie zaaktualizujemy korzenia.
Odczytywania - mamy dwa wskaźniki, jeden jest tuż przed początkiem, a drugi tuż po końcu. Jeżeli pierwszy jest lewym synem to dodajemy do wyniku wartość z wierzchołka o jeden większego. Jeżeli drugi jest prawym synem, to dodajemy do wyniku wartość z wierzchołka o jeden mniejszego. Następnie obydwoma wskaźnikami przechodzimy do ich ojców i powtarzamy algorytm, dopóki nie będą mieli tego samego ojca (czyli dopóki różnica ich numerów jest większa od 1).
Zauważmy, że podstawa drzewa jest potęgą dwójki. Ale co jeśli mamy długość ciągu, która nie jest potęgą dwójki? Po prostu rozszerzamy nasze drzewo do najbliższej potęgi dwójki i wypełniamy to rozszerzenie elementami neutralnymi (w przypadku sumy 0). Jak przechodzić między synem a ojcem, ojcem a synem? (v to numer wierzchołka, w którym się obecnie znajdujemy) Do ojca: v podzielonie całkowicie przez 2; do lewego syna: v * 2, do prawego syna: v * 2 + 1. Takie łatwe przechodzenie między ojcem a synem mamy dzięki numeracji wierzchołków w drzewie. Jak obliczyć jaki numer ma wierzchołek odpowiadający za punkt x? Trzymamy wartość base, która nam mówi ile wierzchołków mamy w podstawie drzewa. Numer wierzchołka odpowiadającego za punkt x to x + base (x+base-1).

Przykład

Zasymulujmy działanie drzewa przedziałowego na przykładowych danych:
Początkowo ciąg to 5 3 4 8
Odczytanie sumy z przedziału 2-4
Aktualizacja elementu 3; z 4 zmienia się na 1
Odczytanie sumy z przedziału 2-3
Aktualizacja elementu 2; z 3 zmienia się na 10
Tak wygląda początkowe drzewo:
Base ma wartość 4.
Odczytanie sumy z przedziału 2-4:
pierwszy wskaźnik: 2 + 4 - 1 - 1 = 4
drugi wskaźnik: 4 + 4 + 1 - 1 = 8
4 jest lewym synem, więc dodajemy do wyniku 3
8 nie byłoby prawym synem, więc nie dodajemy do wyniku nic
4/2 = 2, 8/2 = 4
2 jest lewym synem, więc dodajemy do wyniku 12
4 nie jest prawym synem, więc nie dodajemy do wyniku nic
2/2 = 1, 4/2 = 2, różnica numerów wierzchołków jest równa 1, więc kończymy. Odpowiedź na to zapytanie to 15.
Aktualizacja w elemencie 3:
3+4-1 = 6
Zmieniamy wartość w wierzchołku 6 na 1; 6 / 2 = 3
Zmieniamy wartość w wierzchołku 3 na 1 + 8 = 9; 3 / 2 = 1
Zmieniamy wartość w wierzchołku 1 na 8 + 9 = 17
Zaaktualizowaliśmy 1, więc kończymy aktualizację. Tak wygląda drzewo po tej aktualizacji:
Odczytanie sumy z przedziału 2-3:
pierwszy wskaźnik: 2 + 4 - 1 - 1 = 4
drugi wskaźnik: 3 + 4 + 1 - 1 = 7
4 jest lewym synem, więc dodajemy do wyniku 3
7 jest prawym synem, więc dodajemy do wyniku 6
4/2 = 2, 7/2 = 3, różnica numerów wierzchołków jest równa 1, więc kończymy. Odpowiedź na to zapytanie to 9.
Aktualizacja w elemencie 2:
2+4-1 = 5
Zmieniamy wartość w wierzchołku 5 na 10; 5 / 2 = 2
Zmieniamy wartość w wierzchołku 2 na 10 + 5 = 15; 2 / 2 = 1
Zmieniamy wartość w wierzchołku 1 na 15 + 9 = 24
Zaaktualizowaliśmy 1, więc kończymy aktualizację. Tak wygląda drzewo po tej aktualizacji:

implementacja i złożoność

implementacja w c++:

const int base = 1 << 17;
long long drzewo1[base << 1];

void aktu(int v, long long wart){
drzewo1[v] = wart;
v >>= 1;
while(v > 0){
drzewo1[v] = drzewo1[v * 2];
drzewo1[v] += drzewo1[v * 2 + 1];
v >>= 1;
}
}

int odp(int a, int b){
long long wyni = 0;
a--;
b++;
while(b - a > 1){
if(!(a&1)){
wyni += drzewo1[a + 1];
}
if(b&1){
wyni += drzewo1[b - 1];
}
a >>= 1;
b >>= 1;
}
return wyni;
}

implementacja w python:

base = 2 ** 17
drzewo1 = [0 for i in range(base ** 2)]

def aktuppr(v, wart):
drzewo1[v] = wart
v //= 2
while(v > 0):
drzewo1[v] = drzewo1[v * 2]
drzewo1[v] += drzewo1[v * 2 + 1]
v //= 2

def odpppr(a, b):
wyni = 0
a -= 1
b += 1
while(b - a > 1):
if(a % 2 == 0):
wyni += drzewo1[a + 1]
if(b % 2 == 1):
wyni += drzewo1[b - 1]
a //= 2
b //= 2
return wyni

złożoność:

aktu: O(log₂(n))
odp: O(log₂(n))

Zadania

Przedział-punkt (prp)

Do czego służy?

Drzewo przedział-punkt to struktura służąca do aktualizowania wartości z danych przedziałów a także odczytywania wartości w danym indexie. Dla przykładu, dla danego ciągu chcemy w szybkim czasie móc:
1. Odczytać wartość z danego punktu
2. Zmienić wartości na danym przedziale o x
Drzewo przedział-punkt dla tego typu operacji będzie wykonywało log(n) operacji, gdzie n to długość ciągu. Zauważmy że przy brutalnym rozwiązaniu, czyli po prostu trzymaniu tablicy z wartościami i za każdym razem aktualizowaniu po kolei wartości złożoność byłaby taka:
-odczytanie sumy - O(1)
-zaaktualizowanie wartości - O(n)
Widzimy więc, że takie rozwiązanie nie wystarcza... Ale tutaj przychodzi nam z pomocą właśnie drzewo przedziałowe!

Algorytm

Na początku tworzymy takie samo drzewo binarne, jak w drzewie punkt-przedział. Jeśli chodzi o funkcje, to zamienimy je miejscami: funkcję aktualizującą zmienimy na funkcję odpowiadającą i na odwrót. Czyli funkcja odpowiadająca będzie szła od wierzchołka odpowiadającego za dany punkt i potem do jego ojca itd. Zsumuje przy tym wartości we wszystkich napotkanych wierzchołkach i zwróci tę sumę jako wynik. Z kolei aktualizacja będzie miała dwa wskaźniki. Jeżeli pierwszy jest lewym synem to dodajemy do wierzchołka o jeden większego wartość o ile mamy zaaktualizować. Jeżeli drugi jest prawym synem, to to dodajemy do wierzchołka o jeden mniejszego wartość o ile mamy zaaktualizować. Przechodzenie między wierzchołkami i base tak jest takie same jak w drzewie punkt-przedział.

Przykład

Zasymulujmy drzewo przedział-punkt dla przykładowych danych:
Początkowy ciąg: 5 3 4 8
Operacja odczytania wyniku w 3
Operacja odczytania wyniku w 2
Operacja aktualizacji przedziału 1-3 o 3
Operacja odczytania wyniku w 3
Operacja odczytania wyniku w 2
base = 4
Tak wygląda początkowe drzewo:
Operacja odczytania wyniku w 3:
3+4-1 = 6
Dodajemy do wyniku 4. 6 / 2 = 3
Dodajemy do wyniku 0. 3 / 2 = 1
Dodajemy do wyniku 0. Kończymy algorytm bo odczytaliśmy już z jedynki. Wynik to 4.
Operacja odczytania wyniku w 2:
2+4-1 = 5
Dodajemy do wyniku 3. 5 / 2 = 2
Dodajemy do wyniku 0. 2 / 2 = 1
Dodajemy do wyniku 0. Kończymy algorytm bo odczytaliśmy już z jedynki. Wynik to 3.
Operacja aktualizacji przedziału 1-3 o 3:
pierwszy wskaźnik: 1 + 4 - 1 - 1 = 3
drugi wskaźnik: 3 + 4 + 1 - 1 = 7
3 nie jest lewym synem, więc nie aktualizujemy 4
7 jest prawym synem, więc aktualizujemy 6: 4 + 3 = 7
3/2 = 1, 7/2 = 3
1 nie jest lewym synem, więc nie aktualizujemy 2
3 jest prawym synem, więc aktualizujemy 2: 0 + 3 = 3
1/2 = 0, 3/2 = 1
Różnica numerów wierzchołków jest równa 1, więc kończymy. Tak wygląda drzewo po aktualizacji:
Operacja odczytania wyniku w 3:
3+4-1 = 6
Dodajemy do wyniku 7. 6 / 2 = 3
Dodajemy do wyniku 0. 3 / 2 = 1
Dodajemy do wyniku 0. Kończymy algorytm bo odczytaliśmy już z jedynki. Wynik to 7.
Operacja odczytania wyniku w 2:
2+4-1 = 5
Dodajemy do wyniku 3. 5 / 2 = 2
Dodajemy do wyniku 3. 2 / 2 = 1
Dodajemy do wyniku 0. Kończymy algorytm bo odczytaliśmy już z jedynki. Wynik to 6.

implementacja i złożoność

implementacja w c++:

const int base = 1 << 17;
long long drzewo[base << 1];

void aktu(int a, int b, int c){
a--;
b++;
while(b - a > 1){
if(!(a&1)){
drzewo[a + 1] += c;
}
if(b&1){
drzewo[b - 1] += c;
}
a >>= 1;
b >>= 1;
}
}

int odp(int v){
long long wyni = 0;
while(v > 0){
wyni += drzewo[v];
v >>= 1;
}
return wyni;
}

implementacja w python:

base = 2 ** 17
drzewo = [0 for i in range(base ** 2)]

def odpprp(v):
wyni = 1
while(v > 0):
wyni += drzewo[v]
v //= 2
return wyni

def aktuprp(a, b, c):
a -= 1
b += 1
while(b - a > 1):
if(a % 2 == 0):
drzewo[a + 1] += c
if(b % 2 == 1):
drzewo[b - 1] += c
a //= 2
b //= 2

złożoność:

aktu: O(log₂(n))
odp: O(log₂(n))

Zadania

Zadanie Przedział-punkt