Aktualizacja zakresu + zapytanie o zakres z binarnie indeksowanymi drzewami

10

Próbuję zrozumieć, w jaki sposób drzewa indeksowane binarnie (drzewa fenwick) można modyfikować w celu obsługi zapytań o zakres i aktualizacji zakresu.

Znalazłem następujące źródła:

http://kartikkukreja.wordpress.com/2013/12/02/range-updates-with-bit-fenwick-tree/ http://programmingcontests.quora.com/Tutorial-Range-Updates-in-Fenwick-Tree http : //apps.topcoder.com/forums/? module = Thread & ThreadID = 756271 & start = 0 & mc = 4 # 1579597

Ale nawet po przeczytaniu ich wszystkich nie mogłem zrozumieć, jaki jest cel drugiego drzewa indeksowanego binarnie lub co robi.

Czy ktoś mógłby mi wyjaśnić, w jaki sposób drzewo indeksowane binarnie jest modyfikowane, aby je obsłużyć?

data-structures binary-trees search-trees 1110101001
źródło

Odpowiedzi:

9

Załóżmy, że masz pustą tablicę:

0  0  0  0  0  0  0  0  0  0  (array)
0  0  0  0  0  0  0  0  0  0  (cumulative sums)

I chciałeś zaktualizować zakres od +5 do [3..7]:

0  0  0  5  5  5  5  5  0  0  (array)
0  0  0  5 10 15 20 25 25 25  (desired cumulative sums)

Jak można przechowywać żądane sumy sumaryczne za pomocą 2 drzew indeksowanych binarnie?

Sztuką jest użycie dwóch drzew indeksowanych binarnie, BIT1 i BIT2, gdzie skumulowana suma jest obliczana na podstawie ich zawartości. W tym przykładzie oto, co chcielibyśmy przechowywać w dwóch drzewach:

0   0   0   5   5   5   5   5   0   0  (BIT1)
0   0   0  10  10  10  10  10 -25 -25  (BIT2)

Aby znaleźć sum[i], oblicz to:

sum[i] = BIT1[i] * i - BIT2[i]

Na przykład:

sum[2] = 0*2 - 0 = 0
sum[3] = 5*3 - 10 = 5
sum[4] = 5*4 - 10 = 10
...
sum[7] = 5*7 - 10 = 25
sum[8] = 0*8 - (-25) = 25
sum[9] = 0*9 - (-25) = 25

Aby osiągnąć pożądane wartości BIT1 i BIT2 dla poprzedniej aktualizacji zakresu, wykonujemy 3 aktualizacje zakresu:

  • Musimy dokonać aktualizacji zakresu +5 do wskaźników 3..7 dla BIT1.

  • Musimy dokonać aktualizacji zakresu +10 do wskaźników 3..7 dla BIT2.

  • Musimy dokonać aktualizacji zakresu -25 do indeksów 8..9 dla BIT2.

Teraz zróbmy jeszcze jedną transformację. Zamiast przechowywać wartości pokazane powyżej dla BIT1 i BIT2, w rzeczywistości przechowujemy ich skumulowane sumy. To pozwala nam wykonać powyższe 3 aktualizacje zakresu, dokonując 4 aktualizacji sum skumulowanych:

BIT1sum[3] += 5
BIT1sum[8] -= 5
BIT2sum[3] += 10
BIT2sum[8] -= 35

Ogólnie algorytm dodawania wartości v do zakresu [i..j] byłby:

BIT1sum[i]   += v
BIT1sum[j+1] -= v
BIT2sum[i]   += v * (i-1)
BIT2sum[j+1] -= v * j

gdzie składnia + = i - = oznacza po prostu aktualizację struktury danych zbiorczej sumy BIT o wartość dodatnią lub ujemną przy tym indeksie. Należy pamiętać, że aktualizacja skumulowanej BIT według indeksu ma domyślny wpływ na wszystkie indeksy po prawej stronie tego indeksu. Na przykład:

0 0 0 0 0 0 0 0 0 0 (original)

BITsum[3] += 5

0 0 0 5 5 5 5 5 5 5 (after updating [3])

BITsum[8] -= 5

0 0 0 5 5 5 5 5 0 0 (after updating [8])

Drzewa Fenwick przechowują sumy w drzewie binarnym. Uaktualnienia pokazane powyżej drzewa Fenwick można łatwo znaleźć wO(log⁡n) czas.

JS1
źródło
Jaka była twoja początkowa motywacja do stworzenia BIT2, a następnie sum[i] = BIT1[i] * i - BIT2[i]? Wydaje się, że działa, ale wydaje się tak arbitralny ... jaki wgląd pozwala ci do tego dojść?
1110101001
3
Nie wymyśliłem tego algorytmu. Przeczytałem to tak jak ty. Ale jedną rzeczą, na którą należy zwrócić uwagę, jest to, że po dodaniu aktualizacji zasięgu sumy stają się rosnącą sekwencją (5, 10, 15, 20, ...). BITY nie przechowują tak rosnących sekwencji. Ale jeśli zapiszesz stałą (5) w BIT i pomnożysz wartość BIT przez indeks, otrzymasz rosnącą sekwencję dokładnie tak, jak chcesz. Musisz jednak ustalić początek i koniec sekwencji. Po to jest drugie drzewo.
JS1,
Ogólnie dobrze, ale pomyślałem, że napisałeś „Zamiast przechowywać wartości pokazane powyżej dla BIT1 i BIT2, tak naprawdę przechowujemy ich sumy” - powiedziałbym, że faktycznie robisz coś przeciwnego, tzn. Przechowujesz delty .
j_random_hacker