Bereichsaktualisierung + Bereichsabfrage mit binär indizierten Bäumen

10

Ich versuche zu verstehen, wie binär indizierte Bäume (Fenwick-Bäume) geändert werden können, um sowohl Bereichsabfragen als auch Bereichsaktualisierungen zu verarbeiten.

Ich habe folgende Quellen gefunden:

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

Aber selbst nachdem ich sie alle durchgelesen hatte, konnte ich nicht verstehen, was der Zweck des zweiten binär indizierten Baums ist oder was er tut.

Könnte mir bitte jemand erklären, wie der binär indizierte Baum geändert wird, um diese zu handhaben?

1110101001
quelle

Antworten:

9

Angenommen, Sie hatten ein leeres Array:

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

Und Sie wollten ein Bereichsupdate von +5 auf [3..7] durchführen:

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

Wie können Sie die gewünschten kumulierten Summen mit 2 binär indizierten Bäumen speichern?

Der Trick besteht darin, zwei binär indizierte Bäume, BIT1 und BIT2, zu verwenden, wobei die kumulative Summe aus ihrem Inhalt berechnet wird. In diesem Beispiel würden wir Folgendes in den beiden Bäumen speichern:

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

Um dies zu finden sum[i], berechnen Sie Folgendes:

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

Zum Beispiel:

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

Um die gewünschten BIT1- und BIT2-Werte für die vorherige Bereichsaktualisierung zu erreichen, führen wir drei Bereichsaktualisierungen durch:

  • Wir müssen eine Bereichsaktualisierung von +5 auf die Indizes 3..7 für BIT1 durchführen.

  • Wir müssen eine Bereichsaktualisierung von +10 auf die Indizes 3..7 für BIT2 durchführen.

  • Wir müssen eine Bereichsaktualisierung von -25 auf die Indizes 8..9 für BIT2 durchführen.

Lassen Sie uns jetzt noch eine Transformation durchführen. Anstatt die oben gezeigten Werte für BIT1 und BIT2 zu speichern, speichern wir tatsächlich ihre kumulierten Summen. Auf diese Weise können wir die oben genannten 3 Bereichsaktualisierungen durchführen, indem wir 4 Aktualisierungen der kumulierten Summen vornehmen:

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

Im Allgemeinen wäre der Algorithmus zum Hinzufügen eines Wertes v zu einem Bereich [i..j]:

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

Dabei bedeutet die Syntax + = und - = einfach, die kumulative BIT-Summendatenstruktur mit einem positiven oder negativen Wert an diesem Index zu aktualisieren. Beachten Sie, dass beim Aktualisieren der kumulierten BIT-Summe an einem Index implizit alle Indizes rechts von diesem Index betroffen sind. Zum Beispiel:

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])

Fenwick-Bäume speichern Summen in einem Binärbaum. Es ist einfach, die oben gezeigten Aktualisierungen an einem Fenwick-Baum in .O(logn)

JS1
quelle
Was war Ihre anfängliche Motivation, BIT2 zu erstellen und dann zu haben sum[i] = BIT1[i] * i - BIT2[i]? Es scheint zu funktionieren, aber es scheint so willkürlich zu sein ... welche Einsicht erlaubt es Ihnen, dazu zu kommen?
1110101001
3
Nun, ich habe diesen Algorithmus nicht erfunden. Ich habe es genauso gelesen wie du. Beachten Sie jedoch, dass beim Hinzufügen einer Bereichsaktualisierung Ihre kumulierten Summen zu einer zunehmenden Reihenfolge werden (5, 10, 15, 20, ...). BITs speichern solche zunehmenden Sequenzen nicht. Wenn Sie jedoch eine Konstante (5) in der BIT speichern und den BIT-Wert mit dem Index multiplizieren, erhalten Sie eine zunehmende Reihenfolge, genau wie Sie es möchten. Sie müssen jedoch den Anfang und das Ende der Sequenz festlegen. Dafür ist der zweite Baum da.
JS1
Im Großen und Ganzen gut, aber ich fand es verwirrend, dass Sie geschrieben haben: "Anstatt die oben gezeigten Werte für BIT1 und BIT2 zu speichern, speichern wir tatsächlich ihre kumulierten Summen" - ich würde sagen, dass Sie tatsächlich das Gegenteil tun, dh die Deltas speichern .
j_random_hacker