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