Pohon Fenwick

1. Introduction

Sebuah Pohon Binary-Indexed (Fenwick) adalah sebuah struktur data yang menyediakan metode-metode efisien untuk mengimplementasikan tabel frekuensi kumulatif dinamis.

1-1. Tabel Frekuensi Kumulatif

Seandainya kita mempunyai sebuah multiset bilangan bulat s = {2,4,5,6,5,6,8,6,7,9,7} (tidak harus terurut). Terdapat n = 11 elemen dalam s. Lalu seandainya nilai terbesar yang kita akan pakai adalah m = 10 dan kita tidak akan pernah menggunakan nilai 0. Contohnya, nilai-nilai ini merepresentasikan nilai siswa dari [1..10]. Perhatikan bahwa n independen dari m.

Kita bisa membuat sebuah tabel frekuensi f dari s dengan pengulangan mudah O(n) (ingatlah pass hitungan pertama dari counting sort). Kita bisa membuat sebuah tabel frekuensi kumulatif cf dari tabel frekuensi f dalam O(m) menggunakan teknik mirip dengan DP 1D prefix sum. Contohnya, di tabel berikut, cf[5] = cf[4]+f[5] = 2+2 = 4 lalu cf[6] = cf[5]+f[6] = 4+3 = 7.

1-2. Range Sum Query: rsq(i, j)

Dengan tabel frekuensi kumulatif cf yang demikian, kita bisa melakukan Range Sum Query: rsq(i, j) untuk mengembalikan jumlah dari frekuensi antara indeks i dan j (inklusif), dalam waktu efisien O(1), dengan lagi meggunakan teknik DP 1D prefix sum (bagian prinsip inklusi eksklusi). Sebagai contoh, rsq(5, 9) = rsq(1, 9) - rsq(1, 4) = 11-2 = 9. Karena kunci berikut: 5, 6, 7, 8, dan 9 merepresentasikan nilai, rsq(5, 9) berarti banyaknya siswa (9) yang mendapatkan nilai antara 5 sampai 9 (inklusif).

1-3. Tabel Frekuensi Kumulatif Dinamis

Sebuah struktur data dinamis perlu mendukung (banyak) update di antara kueri. Sebagai contoh, kita dapat update (menambah) frekuensi dari nilai 7 dari 2 → 5 (3 murid lagi mendapatkan nilai 7) dan update (mengurang) frekuensi dari nilai 9 dari 1 → 0 (e.g., 1 murid yang sebelumnya mendapatkan nilai 9 ditemukan telah melakukan plagiarisme dan sekarang dihukum menjadi 0), sehingga memperbarui tabel menjadi:

Sebuah struktur data hanya dengan basis larik untuk mengimplementasikan tabel frekuensi kumulatif dinamis ini akan memerlukan O(m) untuk setiap operasi update. Apakah kita bisa melakukan lebih baik?

2. Mode-mode dan Mode Pertama/Default

Memperkenalkan: Struktur data Pohon Fenwick.

Terdapat tiga mode penggunaan Pohon Fenwick dalam visualisasi ini.

Ide penataan kunci-kunci bilangan bulat yang pintar ini yang pertama kali muncul dalam artikel riset Peter M. Fenwick tahun 1994.

3. Point Update Range Query (PU RQ)

Anda dapat mengklik menu 'Buat' untuk membuat larik frekuensi f dimana f[i] mencatat frekuensi penampakan dari kunci i didalam larik kunci orisinal original s.

PENTING: Larik frekuensi f ini bukan larik orisinal dari kunci-kunci s. Contohnya, jika anda memasukkan {0,1,0,1,2,3,2,1,1,0}, itu berarti anda menciptakan 0 angka satu, 1 angka dua, 0 angka tiga, 1 angka empat, 2 angka lima, ...., 0 angka 10 (indeks berbasis-1). Indeks/kunci bilangan bulat terbesar adalah n = 4 dalam contoh ini.

Jika anda memiliki larik orisinal s dengan n elemen, misalkan {2,4,5,6,5,6,8,6,7,9,7} dari slide-slide sebelumnya (s tidak harus terurut), anda dapat melakukan pass O(n) untuk mengubah s menjadi tabel frekuensi f dengan n indeks/kunci-kunci bilangan bulat. (Kami akan menyediakan metode input alternatif ini di masa mendatang).

3-1. Visualisasi - Bagian 1

Walaupun secara konsep struktur data ini merupakan pohon, implementasinya merupakan sebuah larik berisi bilangan bulat bernama ft yang merentang dari indeks 1 hingga indeks n (kita tidak menggunakan indeks 0 pada larik ft). Nilai-nilai di dalam simpul (dengan garis luar hitam dan bagian dalam putih) dari pohon Fenwick di atas merupakan nilai-nilai yang disimpan dalam larik ft indeks basis 1.

Saat ini, edge dari Pohon Fenwick ini masih belum ditunjukkan. Terdapat dua versi dari pohon ini, pohon interogasi/kueri dan pohon updating.

3-2. Visualisasi - Bagian 2

Nilai-nilai di dalam simpul bagian bawah (bagian dalam berwarna biru) adalah nilai dari larik frekuensi f.

3-3. Visualisasi - Bagian 3

Nilai tersebut disimpan dalam indeks i di larik ft (simpul i di pohon Fenwick). Dalam kata lain, ft[i] merupakan frekuensi kumulatif dari kunci dalam rentang [i-LSOne(i)+1 .. i]. Secara visual, rentang ini direpresentasikan sebagai edge pada (versi interogasi/kueri dari) pohon Fenwick.

Untuk meninjau kembali operasi LSOne(i) = (i) & -(i), lihat halaman visualisasi bitmask kami.

3-4. Contoh: ft[4] = rsq(1, 4)

ft[4] = 2 menyimpan frekuensi kumulatif dari kunci dalam [4-LSOne(4)+1 .. 4].
(ikuti edge dari indeks 4 kembali ke atas menuju indeks 0, ditambah satu indeks).
Ini adalah [4-4+1 .. 4] = [1 .. 4] dan f[1]+f[2]+f[3]+f[4] = 0+1+0+1 = 2.

3-5. Contoh: ft[6] = rsq(5, 6)

ft[6] = 5 menyimpan frekuensi kumulatif dari kunci dalam [6-LSOne(6)+1 .. 6].
(ikuti edge dari indeks 6 kembali ke atas menuju indeks 4, ditambah satu indeks).
Ini adalah [6-2+1 .. 6] = [5 .. 6] dan f[5]+f[6] = 2+3 = 5.

3-6. Range Query: rsq(j)

Fungsi rsq(j) mengembalikan frekuensi kumulatif dari indeks pertama 1 (mengabaikan indeks 0) ke indeks j.

Nilai tersebut merupakan jumlah dari sub-frekuensi yang disimpan dalam larik ft dengan indeks berhubungan dengan j via formula j' = j-LSOne(j). Hubungan ini membentuk sebuah pohon Fenwick, spesifiknya, bagian 'pohon interogasi' dari pohon Fenwick.

Kita menggunakan formula ini secara iterative hingga j adalah 0.

Fungsi ini berjalan dalam O(log m), tidak peduli dengan nilai n. Diskusi: Mengapa?

3-7. Contoh: rsq(6) = ft[6]+ft[4]

Kita telah lihat bahwa ft[6] = rsq(5, 6) dan ft[4] = rsq(1, 4).
Maka, rsq(6) = ft[6] + ft[6-LSOne(6)] = ft[6] + ft[6-2] =
ft[6] + ft[4] = 5 + 2 = 7.
PS: 4-LSOne(4) = 4-4 = 0.

3-8. Range Query: rsq(i, j)

rsq(i, j) mengembalikan frekuensi kumulatif dari indeks i ke j, inklusif.

Jika i = 1, kita bisa menggunakan rsq(j) seperti sebelumnya.
Jika i > 1, kita cukup mengembalikan rsq(j) – rsq(i–1) (Prinsip Inklusi Eksklusi).

Diskusi: Apakah Anda mengerti alasannya?

Fungsi ini juga berjalan dalam O(log m), tidak peduli dengan nilai n. Diskusi: Mengapa?

3-9. Contoh: rsq(4, 6) = rsq(6) - ...

rsq(4, 6) = rsq(6) – [slide selanjutnya...].
Dan kita tahu dari sebelumnya bahwa rsq(6) = ft[6]+ft[4] = 5+2 = 7.

3-10. Contoh: rsq(4, 6) = rsq(6) - rsq(3)

rsq(4, 6) = rsq(6) – rsq(3).
Kita bisa menghitung bahwa rsq(3) = ft[3]+ft[2] = 0+1 = 1.

3-11. Contoh: rsq(4, 6) = 7 - 1 = 6

rsq(4, 6) = rsq(6) – rsq(3) = 7 - 1 = 6.

3-12. Point Update: update(i, v)

Untuk memperbarui frekuensi dari kunci (indeks) i dengan v (v bisa positif atau negatif; |v| tidak harus satu), kita menggunakan update(i, v).

Indeks yang terkait dengan i melalui i' = i + LSOne(i) akan diperbarui dengan v ketika i < ft.size() (Perhatikan bahwa ft.size() adalah m+1 (karena kita mengabaikan indeks 0). Hubungan ini membentuk varian dari struktur Pohon Fenwick yang disebut 'pohon pembaruan'.

Diskusi: Apakah Anda memahami operasi ini dan mengapa kita menghindari indeks 0?

Fungsi ini juga berjalan dalam O(log m), terlepas dari n. Diskusi: Mengapa?

4. Mode Kedua

Mode kedua dari Pohon Fenwick ini adalah mode yang dapat melakukan Range Update (RU) tetapi hanya dapat melakukan Point Query (PQ) dalam O(log N).

Kita menyingkat tipe ini sebagai RU PQ.

5. Range Update Point Query (RU PQ)

5-1. Visualisasi RU PQ

Simpul-simpul diatas menunjukan nilai-nilai yang disimpan dalam Pohon Fenwick (larik ft).

Simpul-simpul dibawah menunjukkan nilai-nilai dari data (tabel frekuensi f).

Catat modifikasi pintar dari Pohon Fenwick yang digunakan dalam tipe RU PQ ini: Kita menambah awal dari range sebesar +1 tetapi mengurangi satu indeks setelah akhir dari range sebesar -1 untuk mencapai hasil ini.

6. Mode Ketiga

Mode ketiga dari Pohon Fenwick ini adalah mode yang dapat melakukan Range Update (RU) dan Range Query (RQ) dalam O(log N), sehingga mode ini berjalan se-efisien Pohon Segmen dengan Lazy Update yang juga dapat melakukan RU RQ dalam O(log N).

7. Range Update Range Query (RU RQ)

Buatlah datanya dan coba jalankan algoritma Range Update atau Range Query pada data tersebut.

Pembuatan data dapat dilakukan dengan memasukkan beberapa interval seperti dalam versi RU PQ. Namun, kali ini anda juga melakukan Range Query secara efisien.

7-1. Visualisasi RU RQ

8. Tambahan-Tambahan

8-1. Implementasi

Sayangnya, struktur data ini belum tersedia di C++ STL, Java API, atau Python Standard Library pada tahun 2020. Maka, kita perlu menulis implementasi kita sendiri.

Silahkan lihat implementasi C++/Python/Java/OCaml dari struktur data Pohon Fenwick ini dalam bentuk Object-Oriented Programming (OOP):
fenwicktree_ds.cpp | py | java | ml

Sekali lagi, anda boleh bebas mengubah implementasi ini sesuai dengan kebutuhan anda.