Pembaruan rentang + kisaran permintaan dengan pohon indeks biner

Saya mencoba untuk memahami bagaimana pohon indeks biner (pohon fenwick) dapat dimodifikasi untuk menangani permintaan rentang dan pembaruan rentang.

Saya menemukan sumber-sumber berikut:

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 = Utas & threadID = 756271 & mulai = 0 & mc = 4 # 1579597

Tetapi bahkan setelah membaca semuanya, saya tidak dapat memahami apa tujuan dari pohon indeks biner kedua atau apa fungsinya.

Bisakah seseorang tolong jelaskan kepada saya bagaimana pohon indeks biner dimodifikasi untuk menangani ini?

Misalkan Anda memiliki array kosong:

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

Dan Anda ingin membuat pembaruan rentang +5 hingga [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)

Bagaimana Anda bisa menyimpan jumlah kumulatif yang diinginkan menggunakan 2 pohon indeks biner?

Caranya adalah dengan menggunakan dua pohon indeks biner, BIT1 dan BIT2, di mana jumlah kumulatif dihitung dari isinya. Dalam contoh ini, inilah yang akan kami simpan di kedua pohon:

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

Untuk menemukan sum[i], Anda menghitung ini:

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

Sebagai contoh:

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

Untuk mencapai nilai BIT1 dan BIT2 yang diinginkan untuk pembaruan rentang sebelumnya, kami melakukan 3 pembaruan rentang:

• Kita perlu melakukan pembaruan rentang +5 ke indeks 3..7 untuk BIT1.

• Kita perlu melakukan pembaruan rentang +10 ke indeks 3..7 untuk BIT2.

• Kita perlu melakukan pembaruan rentang -25 ke indeks 8..9 untuk BIT2.

Sekarang mari kita lakukan satu transformasi lagi. Alih-alih menyimpan nilai yang ditunjukkan di atas untuk BIT1 dan BIT2, kami sebenarnya menyimpan jumlah kumulatif mereka. Ini memungkinkan kami melakukan pembaruan 3 rentang di atas dengan membuat 4 pembaruan pada jumlah kumulatif:

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

Secara umum, algoritma untuk menambahkan nilai v ke rentang [i..j] adalah:

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

di mana sintaks + = dan - = hanya berarti memperbarui struktur data jumlah kumulatif BIT dengan nilai positif atau negatif pada indeks itu. Perhatikan bahwa ketika Anda memperbarui jumlah kumulatif BIT pada indeks, itu secara implisit mempengaruhi semua indeks di sebelah kanan indeks itu. Sebagai contoh:

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

Pohon Fenwick menyimpan jumlah dalam pohon biner. Sangat mudah untuk melakukan pembaruan yang ditunjukkan di atas ke pohon Fenwick, dalam waktu .$O(\log n)$