BIT: Apa intuisi di balik pohon indeks biner dan bagaimana hal itu dipikirkan?

Pohon indeks biner memiliki sangat sedikit atau relatif tidak memiliki literatur dibandingkan dengan struktur data lainnya. Satu-satunya tempat di mana itu diajarkan adalah tutorial topcoder . Meskipun tutorialnya lengkap dalam semua penjelasannya, saya tidak bisa mengerti intuisi di balik pohon seperti itu? Bagaimana itu ditemukan? Apa bukti aktual dari kebenarannya?

Secara intuitif, Anda dapat menganggap pohon indeks biner sebagai representasi terkompresi dari pohon biner yang merupakan optimasi dari representasi array standar. Jawaban ini masuk ke dalam satu kemungkinan derivasi.

Misalkan, misalnya, Anda ingin menyimpan frekuensi kumulatif dengan total 7 elemen berbeda. Anda bisa memulai dengan menuliskan tujuh ember yang nomornya akan dibagikan:

[   ] [   ] [   ] [   ] [   ] [   ] [   ]
  1     2     3     4     5     6     7

Sekarang, misalkan frekuensi kumulatif terlihat seperti ini:

[ 5 ] [ 6 ] [14 ] [25 ] [77 ] [105] [105]
  1     2     3     4     5     6     7

Menggunakan versi array ini, Anda bisa menambah frekuensi kumulatif elemen apa pun dengan meningkatkan nilai angka yang disimpan di tempat itu, lalu menambah frekuensi semua yang datang sesudahnya. Misalnya, untuk meningkatkan frekuensi kumulatif 3 oleh 7, kita bisa menambahkan 7 ke setiap elemen dalam array pada atau setelah posisi 3, seperti yang ditunjukkan di sini:

[ 5 ] [ 6 ] [21 ] [32 ] [84 ] [112] [112]
  1     2     3     4     5     6     7

Masalahnya adalah ini membutuhkan O (n) waktu untuk melakukan ini, yang cukup lambat jika n besar.

Satu cara yang dapat kita pikirkan untuk meningkatkan operasi ini adalah dengan mengubah apa yang kita simpan dalam ember. Daripada menyimpan frekuensi kumulatif hingga titik tertentu, Anda bisa memikirkan untuk hanya menyimpan jumlah yang frekuensi saat ini meningkat relatif terhadap ember sebelumnya. Misalnya, dalam kasus kami, kami akan menulis ulang ember di atas sebagai berikut:

Before:
[ 5 ] [ 6 ] [21 ] [32 ] [84 ] [112] [112]
  1     2     3     4     5     6     7

After:
[ +5] [ +1] [+15] [+11] [+52] [+28] [ +0]
  1     2     3     4     5     6     7

Sekarang, kita dapat menambah frekuensi dalam ember dalam waktu O (1) dengan hanya menambahkan jumlah yang sesuai ke ember itu. Namun, total biaya melakukan pencarian sekarang menjadi O (n), karena kita harus menghitung ulang total dalam ember dengan merangkum nilai dalam semua ember yang lebih kecil.

Wawasan besar pertama yang perlu kita dapatkan dari sini ke pohon indeks biner adalah sebagai berikut: daripada terus-menerus menghitung ulang jumlah elemen array yang mendahului elemen tertentu, bagaimana jika kita harus menghitung jumlah total semua elemen sebelum spesifik poin dalam urutan? Jika kita bisa melakukan itu, maka kita bisa mengetahui jumlah kumulatif pada suatu titik dengan hanya merangkum kombinasi yang tepat dari jumlah yang dihitung sebelumnya ini.

Salah satu cara untuk melakukan ini adalah mengubah representasi dari menjadi array ember menjadi pohon biner node. Setiap node akan diberi catatan dengan nilai yang mewakili jumlah kumulatif semua node di sebelah kiri dari node yang diberikan. Sebagai contoh, misalkan kita membangun pohon biner berikut dari simpul-simpul ini:

             4
          /     \
         2       6
        / \     / \
       1   3   5   7

Sekarang, kita dapat menambah setiap simpul dengan menyimpan jumlah kumulatif semua nilai termasuk simpul itu dan subtree kirinya. Misalnya, mengingat nilai-nilai kami, kami akan menyimpan yang berikut:

Before:
[ +5] [ +1] [+15] [+11] [+52] [+28] [ +0]
  1     2     3     4     5     6     7

After:
                 4
               [+32]
              /     \
           2           6
         [ +6]       [+80]
         /   \       /   \
        1     3     5     7
      [ +5] [+15] [+52] [ +0]

Dengan struktur pohon ini, mudah untuk menentukan jumlah kumulatif hingga titik tertentu. Idenya adalah sebagai berikut: kita memelihara penghitung, awalnya 0, lalu melakukan pencarian biner normal hingga kita menemukan simpul yang dimaksud. Saat kami melakukannya, kami juga yang berikut: setiap saat kami bergerak ke kanan, kami juga menambahkan nilai saat ini ke penghitung.

Sebagai contoh, misalkan kita ingin mencari jumlah untuk 3. Untuk melakukannya, kita melakukan hal berikut:

• Mulai dari root (4). Penghitung adalah 0.
• Ke kiri ke simpul (2). Penghitung adalah 0.
• Ke kanan ke simpul (3). Penghitung adalah 0 + 6 = 6.
• Temukan simpul (3). Penghitung adalah 6 + 15 = 21.

Anda bisa membayangkan juga menjalankan proses ini secara terbalik: mulai dari node yang diberikan, menginisialisasi penghitung ke nilai node itu, lalu berjalan menaiki pohon ke root. Setiap kali Anda mengikuti tautan anak kanan ke atas, tambahkan nilai pada simpul yang Anda tuju. Misalnya, untuk menemukan frekuensi untuk 3, kita dapat melakukan hal berikut:

• Mulai dari simpul (3). Penghitung adalah 15.
• Ke atas ke simpul (2). Penghitung adalah 15 + 6 = 21.
• Ke atas ke simpul (4). Penghitung adalah 21.

Untuk menambah frekuensi suatu simpul (dan, secara implisit, frekuensi dari semua simpul yang mengikutinya), kita perlu memperbarui kumpulan simpul di pohon yang menyertakan simpul itu di subtree kirinya. Untuk melakukan ini, kita lakukan hal berikut: menambah frekuensi untuk simpul itu, lalu mulai berjalan ke akar pohon. Setiap kali Anda mengikuti tautan yang membawa Anda sebagai anak kiri, tambahkan frekuensi simpul yang Anda temui dengan menambahkan nilai saat ini.

Misalnya, untuk menambah frekuensi simpul 1 dengan lima, kami akan melakukan yang berikut:

                 4
               [+32]
              /     \
           2           6
         [ +6]       [+80]
         /   \       /   \
      > 1     3     5     7
      [ +5] [+15] [+52] [ +0]

Mulai dari simpul 1, tambah frekuensinya dengan 5 untuk mendapatkan

                 4
               [+32]
              /     \
           2           6
         [ +6]       [+80]
         /   \       /   \
      > 1     3     5     7
      [+10] [+15] [+52] [ +0]

Sekarang, buka induknya:

                 4
               [+32]
              /     \
         > 2           6
         [ +6]       [+80]
         /   \       /   \
        1     3     5     7
      [+10] [+15] [+52] [ +0]

Kami mengikuti tautan anak kiri ke atas, jadi kami menambah frekuensi simpul ini juga:

                 4
               [+32]
              /     \
         > 2           6
         [+11]       [+80]
         /   \       /   \
        1     3     5     7
      [+10] [+15] [+52] [ +0]

Kami sekarang pergi ke induknya:

               > 4
               [+32]
              /     \
           2           6
         [+11]       [+80]
         /   \       /   \
        1     3     5     7
      [+10] [+15] [+52] [ +0]

Itu adalah tautan anak kiri, jadi kami menambah simpul ini juga:

                 4
               [+37]
              /     \
           2           6
         [+11]       [+80]
         /   \       /   \
        1     3     5     7
      [+10] [+15] [+52] [ +0]

Dan sekarang kita selesai!

Langkah terakhir adalah mengkonversi dari ini ke pohon indeks biner, dan ini adalah di mana kita bisa melakukan beberapa hal menyenangkan dengan angka biner. Mari kita menulis ulang setiap indeks ember di pohon ini dalam biner:

                100
               [+37]
              /     \
          010         110
         [+11]       [+80]
         /   \       /   \
       001   011   101   111
      [+10] [+15] [+52] [ +0]

Di sini, kita bisa melakukan pengamatan yang sangat, sangat keren. Ambil salah satu dari angka-angka biner ini dan temukan 1 terakhir yang diatur dalam angka, lalu jatuhkan bit itu, bersama dengan semua bit yang datang setelahnya. Anda sekarang dibiarkan dengan yang berikut:

              (empty)
               [+37]
              /     \
           0           1
         [+11]       [+80]
         /   \       /   \
        00   01     10   11
      [+10] [+15] [+52] [ +0]

Berikut ini adalah pengamatan yang sangat, sangat keren: jika Anda memperlakukan 0 berarti "kiri" dan 1 berarti "benar," bit yang tersisa pada setiap angka menguraikan dengan tepat cara memulai pada root dan kemudian berjalan ke nomor itu. Sebagai contoh, simpul 5 memiliki pola biner 101. 1 terakhir adalah bit terakhir, jadi kami menjatuhkannya untuk mendapatkan 10. Memang, jika Anda mulai dari root, ke kanan (1), lalu ke kiri (0), Anda berakhir di simpul 5!

Alasan mengapa hal ini penting adalah karena operasi pencarian dan pembaruan kami bergantung pada jalur akses dari node kembali ke root dan apakah kami mengikuti tautan anak kiri atau kanan. Misalnya, saat pencarian, kami hanya peduli dengan tautan yang tepat yang kami ikuti. Selama pembaruan, kami hanya peduli dengan tautan kiri yang kami ikuti. Pohon indeks biner ini melakukan semua ini dengan sangat efisien dengan hanya menggunakan bit dalam indeks.

Trik kuncinya adalah properti berikut dari pohon biner sempurna ini:

Diberikan simpul n, simpul berikutnya pada jalur akses kembali ke akar di mana kita ke kanan diberikan dengan mengambil representasi biner dari n dan menghapus 1 terakhir.

Sebagai contoh, lihat jalur akses untuk simpul 7, yaitu 111. Node pada jalur akses ke root yang kita ambil yang melibatkan mengikuti penunjuk kanan ke atas adalah

• Node 7: 111
• Node 6: 110
• Simpul 4: 100

Semua ini adalah tautan yang benar. Jika kita mengambil jalur akses untuk simpul 3, yaitu 011, dan melihat simpul di mana kita pergi, kita dapatkan

• Node 3: 011
• Simpul 2: 010
• (Node 4: 100, yang mengikuti tautan kiri)

Ini berarti bahwa kita dapat dengan sangat, sangat efisien menghitung jumlah kumulatif hingga ke simpul sebagai berikut:

• Tulis simpul n dalam biner.
• Atur penghitung ke 0.
• Ulangi yang berikut saat n ≠ 0:
  • Tambahkan nilai pada simpul n.
  • Hapus 1 bit paling kanan dari n.

Demikian pula, mari kita pikirkan tentang bagaimana kita akan melakukan langkah pembaruan. Untuk melakukan ini, kami ingin mengikuti jalur akses kembali ke root, memperbarui semua node tempat kami mengikuti tautan kiri ke atas. Kita dapat melakukan ini dengan melakukan algoritma di atas, tetapi mengubah semua 1 ke 0 dan 0 ke 1.

Langkah terakhir dalam pohon indeks biner adalah untuk mencatat bahwa karena tipu daya bitwise ini, kita bahkan tidak perlu memiliki pohon disimpan secara eksplisit lagi. Kita bisa menyimpan semua node dalam array dengan panjang n, kemudian menggunakan teknik memutar-mutar bitwise untuk menavigasi pohon secara implisit. Bahkan, itulah yang dilakukan oleh pohon bitwise yang diindeks - ia menyimpan node dalam sebuah array, kemudian menggunakan trik bitwise ini untuk secara efisien mensimulasikan berjalan ke atas di pohon ini.

Semoga ini membantu!

Saya pikir kertas asli oleh Fenwick jauh lebih jelas. Jawaban di atas oleh @templatetypedef membutuhkan beberapa "pengamatan yang sangat keren" tentang pengindeksan pohon biner yang sempurna, yang membingungkan dan ajaib bagi saya.

Fenwick hanya mengatakan bahwa rentang tanggung jawab setiap simpul dalam pohon interogasi akan sesuai dengan bit terakhir:

Misalnya sebagai set bit terakhir dari 6== 00110adalah "2-bit" itu akan bertanggung jawab untuk rentang 2 node. Untuk 12== 01100, ini adalah "4-bit", jadi itu akan bertanggung jawab untuk rentang 4 node.

Jadi ketika menanyakan F(12)== F(01100), kami menghapus bit satu demi satu, dapatkan F(9:12) + F(1:8). Ini hampir bukan bukti yang ketat, tapi saya pikir itu lebih jelas ketika diletakkan begitu sederhana pada sumbu angka dan bukan pada pohon biner yang sempurna, apa tanggung jawab setiap node, dan mengapa biaya kueri sama dengan jumlah mengatur bit.

Jika ini masih belum jelas kertas sangat dianjurkan.