General: Addendum (Drzewo Fenwicka)

Public message

Alternatywna nazwa drzewa Fenwicka to drzewo potęgowe, a po angielsku Binary Indexed Tree (BIT). Praca naukowa o operacjach przedział-przedział na dodawaniu z Fenwickiem (lub dowolną strukturą przedział-punkt): https://arxiv.org/abs/1311.6093 Nie ma tego na kartce, więc jak ktoś jest ciekawy to zachęcam do przeczytania. Poza tym, zauważcie, że wyprowadzając tę metodę i licząc to dla 2D, wcale nie trzeba rozpatrywać 4 przypadków. Tak jak zaczynałem robiąc przypadek jednowymiarowy wystarczy opracować, jak zmienia się get_prefix(i) przy dodawaniu na jakimś sufiksie [a, n]. Wtedy [a, b] otrzymujemy dodając +x na [a, n] oraz -x na [b+1, n]. Analogicznie, w 2D wystarczy opisać wzorki dla [x1, y1] : [n, n] (czyli to co rozpisałem na tablicy), a [x1, y1] : [x2, y2] wychodzi z zasady włączeń i wyłączeń (tak jak sumy prefiksowe 2D). Oczywiście otrzymane w ten sposób wzory są mniej efektywne – rozpatrując 4 przypadki niektóre współczynniki się zerują, więc w efekcie wykonamy mniej operacji na Fenwicku. Za pomocą Fenwicka łatwo będzie robić hashe dynamicznego ciągu, ale hashe dopiero będą, więc o tym nie wspominałem. Nie wspominałem też o tym, że robiąc Fenwicka 2D zamiast Fenwicka Fenwicków można np. robić Fenwicki specjalnych zbiorów (PBDS tree z order statistics) – powiemy jeszcze o nich w przyszłości. A po co komu Fenwick? Podsumujmy: + mniejsze zużycie pamięci + średnio szybszy + łatwiejszy i krótszy do zaklepania + elegancki (punkty stylu) + dużo prostszy i szybszy wariant wielowymiarowy - wszystko, co można osiągnąć Fenwickiem, można osiągnąć drzewem przedziałowym w takiej samej złożoności. A w praktyce gdzie zrobi się Fenwicka? Może w jakiejś implementacji prostej bazy danych, gdzie pozwalałby np. na efektywne zapytania o to, ile jest krotek których wartości są w podanych przedziałach (dla wielowymiarowego drzewa).