Sebuah Pohon Binary-Indexed (Fenwick) adalah sebuah struktur data yang menyediakan metode-metode efisien untuk mengimplementasikan tabel frekuensi kumulatif dinamis.
Remarks: By default, we show e-Lecture Mode for first time (or non logged-in) visitor.
If you are an NUS student and a repeat visitor, please login.
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.
| Indeks/Nilai/Simbol | Frekuensi f | Frekuensi kumulatif cf |
|---|---|---|
| 0 | - | - (indeks 0 diabaikan) |
| 1 | 0 | 0 |
| 2 | 1 | 1 |
| 3 | 0 | 1 |
| 4 | 1 | 2 |
| 5 | 2 | 4 == cf[4]+f[5] |
| 6 | 3 | 7 == cf[5]+f[6] |
| 7 | 2 | 9 |
| 8 | 1 | 10 |
| 9 | 1 | 11 |
| 10 == m | 0 | 11 == n |
Pro-tip 1: Since you are not logged-in, you may be a first time visitor (or not an NUS student) who are not aware of the following keyboard shortcuts to navigate this e-Lecture mode: [PageDown]/[PageUp] to go to the next/previous slide, respectively, (and if the drop-down box is highlighted, you can also use [→ or ↓/← or ↑] to do the same),and [Esc] to toggle between this e-Lecture mode and exploration mode.
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).
| Indeks/Nilai/Simbol | Frekuensi f | Frekuensi Kumulatif cf |
|---|---|---|
| 0 | - | - (indeks 0 diabaikan) |
| 1 | 0 | 0 |
| 2 | 1 | 1 |
| 3 | 0 | 1 |
| 4 | 1 | 2 == rsq(1, 4) |
| 5 | 2 | 4 |
| 6 | 3 | 7 |
| 7 | 2 | 9 |
| 8 | 1 | 10 |
| 9 | 1 | 11 == rsq(1, 9) |
| 10 == m | 0 | 11 == n |
Pro-tip 2: We designed this visualization and this e-Lecture mode to look good on 1366x768 resolution or larger (typical modern laptop resolution in 2021). We recommend using Google Chrome to access VisuAlgo. Go to full screen mode (F11) to enjoy this setup. However, you can use zoom-in (Ctrl +) or zoom-out (Ctrl -) to calibrate this.
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:
| Indeks/Nilai/Simbol | Frekuensi f | Frekuensi Kumulatif cf |
|---|---|---|
| 0 | - | - (indeks 0 diabaikan) |
| 1 | 0 | 0 |
| 2 | 1 | 1 |
| 3 | 0 | 1 |
| 4 | 1 | 2 |
| 5 | 2 | 4 |
| 6 | 3 | 7 |
| 7 | 2 → 5 | 9 → 12 |
| 8 | 1 | 10 → 13 |
| 9 | 1 → 0 | 11 → 13 |
| 10 == m | 0 | 11 → 13 == n |
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?
Pro-tip 3: Other than using the typical media UI at the bottom of the page, you can also control the animation playback using keyboard shortcuts (in Exploration Mode): Spacebar to play/pause/replay the animation, ←/→ to step the animation backwards/forwards, respectively, and -/+ to decrease/increase the animation speed, respectively.
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.
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).
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.
Nilai-nilai di dalam simpul bagian bawah (bagian dalam berwarna biru) adalah nilai dari larik frekuensi f.
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.
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.
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.
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?
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.
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?
rsq(4, 6) = rsq(6) – [slide selanjutnya...].
Dan kita tahu dari sebelumnya bahwa rsq(6) = ft[6]+ft[4] = 5+2 = 7.
rsq(4, 6) = rsq(6) – rsq(3).
Kita bisa menghitung bahwa rsq(3) = ft[3]+ft[2] = 0+1 = 1.
rsq(4, 6) = rsq(6) – rsq(3) = 7 - 1 = 6.
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?
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.
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.
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).
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.
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.
You have reached the last slide. Return to 'Exploration Mode' to start exploring!
Note that if you notice any bug in this visualization or if you want to request for a new visualization feature, do not hesitate to drop an email to the project leader: Dr Steven Halim via his email address: stevenhalim at gmail dot com.
Buat - O(m log m)
Buat - O(m)
RSQ(i, j)
Update(i, v)