znalazłem this answer przez @templatetypedef bardzo jasno tłumaczyć o intuicji i dowód indeksowanego binarnego drzewa: Odpowiedź ....
Intuicyjnie można myśleć o indeksowanej binarnego drzewa jako skompresowanej reprezentacji drzewo binarne, które samo w sobie jest optymalizacją standardowej reprezentacji tablic. Ta odpowiedź przechodzi do jednego możliwego wyprowadzenia.
Załóżmy na przykład, że chcesz przechowywać skumulowane częstotliwości dla łącznie 7 różnych elementów. Można zacząć od wypisywanie siedem wiadra, do którego zostaną rozdzielone numery:
[ ] [ ] [ ] [ ] [ ] [ ] [ ]
1 2 3 4 5 6 7
Teraz załóżmy, że skumulowane częstości wyglądać następująco:
[ 5 ] [ 6 ] [14 ] [25 ] [77 ] [105] [105]
1 2 3 4 5 6 7
Stosując tę wersję tablicy , możesz zwiększyć skumulowaną częstotliwość dowolnego elementu, zwiększając wartość liczby przechowywanej w tym miejscu, a następnie zwiększając częstotliwość wszystkiego, co nadejdzie później. Na przykład, w celu zwiększenia skumulowaną częstość 3 o 7, to można dodać 7 do każdego elementu w szyku w trakcie lub po położeniu 3, jak pokazano poniżej:
[ 5 ] [ 6 ] [21 ] [32 ] [84 ] [112] [112]
1 2 3 4 5 6 7
Problem polega na tym, że zajmuje O (n) czas na zrobienie tego, co jest dość powolne, jeśli n jest duże.
Jednym ze sposobów, w jaki możemy poprawić tę operację, jest zmiana zawartości w zasobnikach. Zamiast magazynować skumulowaną częstotliwość do danego punktu, można zamiast tego myśleć o po prostu przechowywaniu ilości, która została zwiększona w stosunku do poprzedniej wielkości. Na przykład, w naszym przypadku, chcemy przepisać powyższe wiadra następująco:
Teraz możemy zwiększyć częstotliwość w wiadrze w czasie O (1), po prostu dodając odpowiednią ilość do tego wiadra. Jednak całkowity koszt wykonania wyszukiwania staje się teraz O (n), ponieważ musimy przeliczyć całą sumę w zasobniku, sumując wartości we wszystkich mniejszych zasobnikach.
Pierwsza ważna informacja, jaką musimy uzyskać z tego miejsca do drzewa indeksowanego binarnie, jest następująca: zamiast ciągłego przeliczania sumy elementów tablicy poprzedzających dany element, co by było, gdybyśmy mieli wstępnie obliczyć całkowitą sumę wszystkich elementów elementy przed określonymi punktami w sekwencji? Gdybyśmy mogli to zrobić, moglibyśmy obliczyć łączną sumę w danym punkcie, po prostu podsumowując właściwą kombinację tych wstępnie zakomponowanych sum.
Jednym ze sposobów, aby to zrobić, jest zmiana reprezentacji z tablicy na segmenty na binarne drzewo węzłów. Każdy węzeł zostanie opatrzony adnotacją wartością reprezentującą łączną sumę wszystkich węzłów po lewej stronie danego węzła.Na przykład, załóżmy, że skonstruować następującą drzewo binarne z tych węzłów:
4
/ \
2 6
/\ /\
1 3 5 7
Teraz możemy poszerzyć każdy węzeł przechowując skumulowaną sumę wszystkich wartości w tym węźle i jego lewym poddrzewie. Na przykład, biorąc pod uwagę nasze wartości, będziemy przechowywać następujące:
Before:
[ +5] [ +1] [+15] [+11] [+52] [+28] [ +0]
1 2 3 4 5 6 7
After:
4
[+32]
/ \
2 6
[ +6] [+80]
/ \ / \
1 3 5 7
[ +5] [+15] [+52] [ +0]
Biorąc to pod uwagę strukturę drzewa, to jest łatwe do ustalenia skumulowanej sumy aż do pewnego momentu. Pomysł jest następujący: utrzymujemy licznik, początkowo 0, a następnie wykonujemy normalne wyszukiwanie binarne, aż znajdziemy dany węzeł. Gdy to robimy, mamy również następujące rzeczy: za każdym razem, gdy poruszamy się w prawo, dodajemy również bieżącą wartość do licznika.
Na przykład, załóżmy, że chcemy sprawdzić sumę do 3. Aby to zrobić, wykonaj następujące czynności:
- Zacznij od korzenia (4). Licznik to 0.
- Idź w lewo do węzła (2). Licznik to 0.
- Idź w prawo do węzła (3). Licznik to 0 + 6 = 6.
- Znajdź węzeł (3). Licznik to 6 + 15 = 21.
Można również wyobrazić sobie uruchomienie tego procesu w odwrotnym kierunku: począwszy od danego węzła, zainicjować licznik do wartości tego węzła, a następnie podejść do drzewa do katalogu głównego. Za każdym razem, gdy podążasz za właściwym linkiem podrzędnym w górę, dodaj wartość w węźle, do którego przybyłeś. Na przykład, aby znaleźć częstotliwość 3, możemy wykonać następujące czynności:
- Rozpocznij w węźle (3). Licznik jest 15.
- Przejdź do góry do węzła (2). Licznik to 15 + 6 = 21.
- Przejdź do góry do węzła (1). Licznik to 21.
Aby zwiększyć częstotliwość węzła (i, niejawnie, częstotliwości wszystkich węzłów, które nadejdą po nim), musimy zaktualizować zestaw węzłów w drzewie, które zawierają ten węzeł w jego pozostawione poddrzewo. Aby to zrobić, wykonaj następujące czynności: zwiększ częstotliwość dla tego węzła, a następnie rozpocznij podchodzenie do katalogu głównego drzewa. Za każdym razem, gdy podążysz za łączem, który zabierze Cię jako lewe dziecko, zwiększ częstotliwość odwiedzanego węzła, dodając bieżącą wartość.
Na przykład, aby zwiększyć częstotliwość węzła 1 przez pięć, chcemy wykonać następujące czynności:
4
[+32]
/ \
2 6
[ +6] [+80]
/ \ / \
> 1 3 5 7
[ +5] [+15] [+52] [ +0]
Zaczynając od węzła 1, zwiększyć częstotliwość o 5, aby uzyskać
4
[+32]
/ \
2 6
[ +6] [+80]
/ \ / \
> 1 3 5 7
[+10] [+15] [+52] [ +0]
teraz , przejdź do jednostki nadrzędnej:
4
[+32]
/ \
> 2 6
[ +6] [+80]
/ \ / \
1 3 5 7
[+10] [+15] [+52] [ +0]
Podążamy za lewym linkiem podrzędnym w górę, więc zwiększamy wartość tego węzła fr equency także:
4
[+32]
/ \
> 2 6
[+11] [+80]
/ \ / \
1 3 5 7
[+10] [+15] [+52] [ +0]
Teraz przejdź do swojego rodzica:
> 4
[+32]
/ \
2 6
[+11] [+80]
/ \ / \
1 3 5 7
[+10] [+15] [+52] [ +0]
To była lewa ogniwo dziecko, więc przyrost ten węzeł, a także:
4
[+37]
/ \
2 6
[+11] [+80]
/ \ / \
1 3 5 7
[+10] [+15] [+52] [ +0]
i teraz gotowe!
Ostatnim krokiem jest zamiana z tego na binarne indeksowane drzewo, i to jest miejsce, w którym możemy robić fajne rzeczy z liczbami binarnymi. Przepisujemy teraz każdy indeks zasobnika w tym drzewie w postaci binarnej:
100
[+37]
/ \
010 110
[+11] [+80]
/ \ / \
001 011 101 111
[+10] [+15] [+52] [ +0]
Tutaj możemy zrobić bardzo, bardzo fajną obserwację. Weź dowolny z tych liczb binarnych i znajdź ostatnie 1, które zostało ustawione w numerze, a następnie upuść ten bit, wraz ze wszystkimi bitami, które nadejdą po nim. Grasz teraz w lewo z następujących czynności:
(empty)
[+37]
/ \
0 1
[+11] [+80]
/ \ / \
00 01 10 11
[+10] [+15] [+52] [ +0]
Tutaj jest naprawdę fajne spostrzeżenie: jeśli traktować 0 oznacza „lewy”, a 1 oznacza „prawo”, a pozostałe bity na każdy numer przeliterować dokładnie jak zacząć od korzenia, a następnie przejść do tej liczby. Na przykład, węzeł 5 ma binarny wzorzec 101. Ostatni 1 jest ostatnim bitem, więc upuszczamy go, aby uzyskać 10. Rzeczywiście, jeśli zaczynasz od korzenia, idź w prawo (1), a następnie w lewo (0), koniec w węźle 5!
Powód, dla którego jest to znaczące, polega na tym, że nasze operacje wyszukiwania i aktualizacji zależą od ścieżki dostępu od węzła z powrotem do katalogu głównego i od tego, czy śledzimy lewe czy prawe odsyłacze podrzędne. Na przykład podczas wyszukiwania, dbamy tylko o linki, które śledzimy. Podczas aktualizacji dbamy tylko o właściwe linki, które śledzimy. To binarnie indeksowane drzewo wykonuje to wszystko super wydajnie, używając tylko bitów w indeksie.
Kluczem Sztuką jest następująca własność tego doskonałego drzewa binarnego:
danego węzła n, następny węzeł na ścieżce dostępu powrotem do korzeni, w którym idziemy w prawo jest podana poprzez binarny reprezentacja n i usunięcie ostatniego 1.
Na przykład spójrz na ścieżkę dostępu dla węzła 7, który ma numer 111.Węzły na drodze dojazdowej do korzeni, które bierzemy, które dotyczą następujących prawo wskaźnik w górę jest
- Węzeł 7: 111
- Węzeł 6: 110
- węzła 4: 100
Wszystkie te są właściwe linki. Jeżeli weźmiemy pod uwagę ścieżkę dostępu do węzła 3, która jest 011, i spojrzeć na węzłach, gdzie mamy iść w prawo, mamy
- Node 3: 011
- Węzeł 2: 010
- (Node 4 : 100, co następuje lewy odnośnik)
oznacza to, że możemy bardzo skutecznie obliczyć skumulowaną sumę aż do węzła w następujący sposób:
- Wypisanie węzła n w systemie binarnym.
- Ustaw licznik 0.
- powtórzyć po while n ≠ 0:
- Dodaj wartości w węźle n.
- Usuń lewy 1 bit od n.
Podobnie, pomyślmy o tym, jak chcemy zrobić krok aktualizacji. Aby to zrobić, chcielibyśmy podążać ścieżką dostępu z powrotem do katalogu głównego, aktualizując wszystkie węzły, w których podążaliśmy za lewym linkiem w górę. Możemy to zrobić, wykonując powyższy algorytm, ale przełączając wszystkie 1 na 0 i 0 na 1.
Ostatnim krokiem w drzewie indeksowanym binarnie jest zwrócenie uwagi, że z powodu tej sztuczki bitowej nie musimy już więcej przechowywać drzewa. Możemy po prostu przechowywać wszystkie węzły w tablicy o długości n, a następnie użyć techniki bitowego twiddling do pośredniego nawigowania po drzewie. W rzeczywistości jest to dokładnie to, co drzewo indeksowane bitowo - przechowuje węzły w tablicy, a następnie używa tych bitowych trików, aby wydajnie symulować chodzenie w górę w tym drzewie.
Mam nadzieję, że to pomoże!
Wikipedia dostarcza raczej powolnego wyjaśnienia: http://en.wikipedia.org/wiki/Fenwick_tree – tjameson
nic nie mówi o algorytmie, który jest faktycznie stosowany, i nic z poprawności algorytmu. –
Jest nie mniej niż krótszy. Pomaga uzyskać istotę algorytmu. Wysłałem to dla innych potencjalnych odbierających. – tjameson