Fibonacci Sequence

Problem sumy przeczyszczonej i dlaczego proste tablice zawodzą

Suma przeczyszczona (lub suma bieżąca) na pozycji i to suma wszystkich elementów tablicy od początku do i. W wielu problemach trzeba odpowiadać na wiele zapytań o sumę przeczyszczoną lub sumę zakresu, a dane podstawowe stale się zmieniają. Przy prostej tablicy istnieją dwie oczywiste strategie, każda z nich szybka w wykonywaniu tylko jednej z tych zadań. Strategia pierwsza: przechowywać surowe dane tablicy i obliczać sumę od nowa za każdym razem, gdy ktoś o to zadaje pytanie, przechodząc przez wszystkie elementy w zakresie. Aktualizacje są natychmiastowe, ale zapytanie o duży zakres zajmuje czas proporcjonalny do rozmiaru tego zakresu, co jest niedopuszczalne, jeśli odpowiada się na tysiące zapytań nad milionami elementów. Strategia druga: obliczyć sumę przeczyszczoną raz, tak aby każde zapytanie było pojedynczym odejmowaniem. Jednak pojedyncza aktualizacja jednego elementu wymusza ponowne obliczenie wszystkich sum przeczyszczonych po nim, co ponownie kosztuje czas proporcjonalny do rozmiaru tablicy. Żaden z tych podejść nie skaluje się, gdy aktualizacje i zapytania są przeplatające i częste, co jest dokładnie sytuacją w analizie danych w czasie rzeczywistym, tickerach finansowych lub problemach konkursowych algorytmicznych. Drzewo Fenwicka łamie ten kompromis, nie przechowując ani surowych wartości, ani pełnych sum przeczyszczonych, ale starannie dobrany zestaw sum częściowych, z których każdy odpowiada za określony, binarnie ułożony fragment tablicy, tak aby obie operacje dotykały tylko nielicznych fragmentów.

Trójka Najniższego Ustawionego Bita

Serce drzewa Fenwicka to pojedyncza operacja bitowa: izolowanie najniższego ustawionego bita indeksu, czyli prawego 1-bita w jego reprezentacji binarnie. Dla danego indeksu i wartość ta jest obliczana jako i & (negacja i), często zapisywane jako i & -i w kodzie, i zawsze równa się potędze dwójki. Ten jeden numer mówi strukturze dokładnie, ile oryginalnych elementów tablicy odpowiada dane slotowi drzewa. Slot 6, którego reprezentacja binarna to 110, ma najniższy ustawiony bit 2, więc przechowuje sumę bloku o 2 elementach. Slot 8, binarny 1000, ma najniższy ustawiony bit 8, więc przechowuje sumę pełnego bloku o 8 elementach. Slot 5, binarny 101, ma najniższy ustawiony bit 1, więc przechowuje tylko własną pojedynczą wartość. Ten wzorzec nie jest przypadkowy: wynika on bezpośrednio z tego, jak liczby binarne rozkładają się na potęgi dwójki i gwarantuje, że każdą sumę przedziałową można odtworzyć przy użyciu maksymalnie log n takich bloków, a każda pojedyncza aktualizacja dotyka maksymalnie log n takich bloków. Elegancją jest to, że ta sama prosta operacja arytmetyczna, stosowana wielokrotnie, napędza oba kierunki struktury: odejmowanie najniższego ustawionego bita prowadzi w stronę początku tablicy dla zapytań, a dodawanie prowadzi w stronę końca dla aktualizacji.

Jak rozprzestrzeniają się aktualizacje

Gdy wartość w pozycji i oryginalnego tablicy ulega zmianie, drzewo Fenwick musi zaktualizować wszystkie sloty sum częściowych, których blok zawiera pozycję i. Rozpoczyna się od indeksu i samego siebie, aplikuje zmianę, a następnie powtarza dodawanie najniższego ustawionego bitu, aby przejść do następnego slotu, który również obejmuje pozycję i, aplikując tam tę samą zmianę, i kontynuuje to, aż indeks przejdzie poza koniec tablicy. Ponieważ każdy skok przynajmniej podwaja rozmiar dotkniętego bloku, łańcuch tych aktualizacji ma długość proporcjonalną do log n nawet dla tablicy z milionami wpisów. Konkretnie, aktualizacja pozycji 5 w drzewie o 8 elementach dotyczy slotu 5 (rozmiar bloku 1), następnie slotu 6 (rozmiar bloku 2, ponieważ 5 + 1 = 6), a następnie slotu 8 (rozmiar bloku 8, ponieważ 6 + 2 = 8) i zatrzymuje się, ponieważ 8 już obejmuje całą tablicę. Zaktualizowano trzy sloty zamiast potencjalnie tysięcy. To jest połowa aktualizacji drzewa Fenwick: zamiast z niecierpliwością utrzymywać pełną tablicę sum częściowych, dotyka tylko niewielki zestaw bloków, którego pokrycie przypadkiem obejmuje zmienioną pozycję, odkładając pracę łączenia wartości do momentu, aż zapytanie faktycznie o to prosi.

Jak akumulują się zapytania

Obliczanie sumy predyktywnej do pozycji i działa jako lustrzane odbicie procesu aktualizacji. Rozpoczynając od indeksu i, algorytm odczytuje wartość przechowywaną w tym miejscu, następnie odejmuje najniższą bitę, aby skoczyć do miejsca zajmującego blok tuż przed nim, dodaje tę wartość, i powtarza to, aż indeks osiągnie zero. Każde odejmowanie zmniejsza indeks o co najmniej połowę, więc ten ruch również zajmuje czas proporcjonalny do log n. Na przykład, suma predyktywna do pozycji 7 w drzewie o 8 elementach odczytuje miejsce 7 (pokrywające tylko pozycję 7), następnie skacze do miejsca 6 (pokrywającego pozycje 5 do 6, ponieważ 7 minus 1 równa się 6), następnie skacze do miejsca 4 (pokrywającego pozycje 1 do 4, ponieważ 6 minus 2 równa się 4), i zatrzymuje się tam, ponieważ 4 minus 4 równa się 0. Dodanie tych trzech przechowywanych wartości daje dokładną sumę pozycji od 1 do 7 bez dotykania siedmiu oryginalnych elementów pojedynczo. Suma zakresu od pozycji a do pozycji b, włącznie, to po prostu suma predyktywna do pozycji b pomniejszona o sumę predyktywną do pozycji a minus 1, więc zarówno aktualizacje punktowe, jak i losowe zapytania dotyczące zakresu redukują się do niewielkiej liczby operacji wyszukiwania w tablicy i dodawania.

Przykładowe Rozwiązanie i Zastosowania w Realnym Świecie

Rozważmy tablicę o 8 elementach z wartościami [3, 2, -1, 6, 5, 4, -3, 3]. Budowa drzewa Fenwick oznacza wstawienie każdego elementu na jego własnym indeksie i umożliwienie jego propagacji w górę dokładnie tak jak aktualizacja, co skutkuje tym, że slot 1 przechowuje wartość 3, slot 2 przechowuje 5 (pozycje 1 do 2), slot 3 przechowuje -1 (własną wartość), slot 4 przechowuje 10 (pozycje 1 do 4), slot 5 przechowuje 5, slot 6 przechowuje 9 (pozycje 5 do 6), slot 7 przechowuje -3 i slot 8 przechowuje 19 (pozycje 1 do 8, suma całkowita). Zapytanie o sumę elementów przed określoną pozycją (w tym przypadku 6) przechodzi przez slot 6 (9) oraz slot 4 (10), co daje łączną wartość 19 pomniejszoną o ogon, prawidłowo odzwierciedlając wartości od pozycji 1 do 6. Ta struktura pojawia się nieustannie poza klasą nauki. W programowaniu konkurencyjnym jest to standardowe narzędzie do odpowiadania na wiele zapytań o sumę zakresów w połączeniu z aktualizacjami punktowymi w czasie log(n). Jest również siłą napędową liczenia rozłącznie (inwersji) w tablicy, klasycznego podprogramu w analizie związaną z sortowaniem i mierzącego, jak bardzo sekwencja jest 'nierozkładowa'. A w statystyce i inżynierii danych, drzewa Fenwick wspierają tablice częstotliwości i struktury statystyk uporządkowanych, pozwalając na utrzymywanie bieżącej histogramu i szybkie odpowiadanie na pytanie 'ile wartości dotychczas widzianych jest mniejszych niż x' w miarę przychodzenia nowych danych.'

Często zadawane pytania

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Fenwick Trees (Binary Indexed Trees): Fast Running Totals i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.