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.
Introducing: Fenwick Tree data structure.
There are three mode of usages of Fenwick Tree in this visualization.
The first mode is the default Fenwick Tree that can handle both Point Update (PU) and Range Query (RQ) in O(log m) where m is the largest (integer) index/key in the data structure. Remember that the actual number of keys in the data structure is denoted by another variable n. We abbreviate this default type as PU RQ that simply stands for Point Update Range Query.
This clever arrangement of integer keys idea is the one that originally appears in Peter M. Fenwick's 1994 paper.
You can click the 'Create' menu to create a frequency array f where f[i] denotes the frequency of appearance of key i in our original array of keys s.
IMPORTANT: This frequency array f is not the original array of keys s. For example, if you enter {0,1,0,1,2,3,2,1,1,0}, it means that you are creating 0 one, 1 two, 0 three, 1 four, 2 fives, ..., 0 ten (1-based indexing). The largest index/integer key is m = 10 in this example as in the earlier slides.
If you have the original array s of n elements, e.g., {2,4,5,6,5,6,8,6,7,9,7} from the earlier slides (s does not need to be necessarily sorted), you can do an O(n) pass to convert s into frequency table f of m indices/integer keys. (We will provide this alternative input method in the near future).
You can click the 'Randomize' button to generate random frequencies of m keys.
Click 'Go' to iteratively call n operations of update(i, f[i]). (We will provide a faster build FT feature in the near future).
Although conceptually this data structure is a tree, it will be implemented as an integer array called ft that ranges from index 1 to index m (we sacrifice index 0 of our ft array). The values inside the (black outline and white inner) vertices of the Fenwick Tree shown above are the values stored in the 1-based Fenwick Tree ft array.
Currently the edges of this Fenwick Tree are not shown yet. There are two versions of the tree, the interrogation/query tree and the updating Tree.
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)