Bagaimana Cara Mengimplementasikan Fenwick Tree untuk Dynamic Prefix Sums dan Weighted Selection?

1. Pertanyaan

Anda memiliki tabel frekuensi dinamis dengan panjang n. Nilai pada posisi-posisi tertentu sering ditingkatkan, dan sistem harus menjawab prefix sums, range sums, serta menemukan posisi yang memuat unit ke-k dari bobot kumulatif. Implementasikan Fenwick Tree (Binary Indexed Tree) dengan O(log n) point updates dan prefix queries, serta bandingkan dengan array prefix biasa dan segment tree.

2. Batasan dan klarifikasi

• Gunakan one-based indexing secara internal; API publik dapat menerima posisi berbasis nol (zero-based) tetapi harus mengonversinya tepat satu kali.
• Pembaruan dapat berupa delta atau selisih dari nilai baru; nyatakan apakah nilai negatif diperbolehkan.
• Peringkat dimulai dari 1. Weighted selection hanya didefinisikan ketika semua bobot bernilai non-negatif dan totalnya minimal k.
• Diskusikan struktur single-threaded terlebih dahulu; pembaruan konkuren memerlukan kunci (lock) atau sharding dan tidak dapat mengasumsikan penulisan integer biasa membentuk snapshot yang konsisten.

3. Ide utama

Entri i menyimpan jumlah dari rentang kontinu yang panjangnya adalah lowbit(i) = i & -i. Kueri prefix berulang kali mengurangkan lowbit, sedangkan point update berulang kali menambahkan lowbit, sehingga masing-masing menyentuh O(log n) posisi array. Range sum adalah selisih dari dua prefix. Ketika array awal diketahui, propagasikan setiap nilai ke indeks induknya untuk membangun dalam O(n).

4. Implementasi referensi

class Fenwick:
  init(values):
    tree = [0] * (len(values) + 1)
    for i from 1 to len(values):
      tree[i] += values[i - 1]
      parent = i + lowbit(i)
      if parent < len(tree):
        tree[parent] += tree[i]

  add(index0, delta):
    i = index0 + 1
    while i < len(tree):
      tree[i] += delta
      i += lowbit(i)

  prefixSum(index0Exclusive):
    total = 0
    i = index0Exclusive
    while i > 0:
      total += tree[i]
      i -= lowbit(i)
    return total

  rangeSum(left0, right0Exclusive):
    return prefixSum(right0Exclusive) - prefixSum(left0)

Untuk weighted selection, lakukan pelacakan dari langkah biner tertinggi. Jika berpindah ke indeks kandidat mempertahankan jumlah kumulatif di bawah k, terima langkah tersebut dan kurangi jumlahnya dari k; indeks akhir ditambah satu adalah posisi yang memuat peringkat k. Ini membutuhkan jumlah kumulatif yang monotonik dan oleh karena itu tidak dapat digunakan secara langsung dengan bobot negatif.

5. Kompleksitas dan trade-off

Fenwick Tree menggunakan array O(n). Point addition, prefix sums, dan weighted selection bernilai O(log n), sedangkan konstruksi linear bernilai O(n). Struktur ini lebih ringkas dan sering kali memiliki konstanta yang lebih kecil daripada segment tree, tetapi secara alami mengekspresikan agregat prefix yang dapat dibalik (reversible) daripada range minima, range updates yang kompleks, atau metadata segmen yang kaya. Untuk data read-only, array prefix biasa menjawab kueri dalam O(1); Fenwick menjadi sangat berharga saat pembaruan sering terjadi.

6. Verifikasi dan observabilitas

• Bandingkan setiap add, prefixSum, dan rangeSum dengan array naif pada input acak, termasuk kasus kosong, elemen tunggal (singleton), dan indeks terakhir.
• Uji semua nol, bobot yang sangat besar, total yang tepat sama dengan k, k di luar batas, dan indeks yang tidak valid.
• Lakukan uji silang antara konstruksi linear dan point additions berulang, lalu bandingkan array internal dan hasil kueri.
• Hasilkan bobot acak non-negatif untuk weighted selection dan periksa batas prefix untuk setiap k; tolak input berbobot negatif secara terpisah.

7. Kesalahan umum

• Mencampur indeks berbasis nol dan berbasis satu sehingga posisi nol terlewat atau posisi terakhir meluap (overflow).
• Memperlakukan i & -i sebagai trik negasi tanpa menjelaskan bahwa itu mengekstrak blok biner terendah.
• Menggunakan weighted selection dengan nilai negatif meskipun jumlah kumulatif tidak lagi monotonik.
• Menimpa simpul pohon dengan nilai baru alih-alih menambahkan delta di sepanjang jalur pembaruan.

8. Poin penilaian wawancara

Menjelaskan lowbit dan cakupan rentang

Kandidat harus menyatakan rentang kontinu mana yang disimpan setiap simpul dan mengapa kueri serta pembaruan mengikuti lompatan lowbit.

Menulis implementasi tanpa kesalahan batas (boundary errors)

Jawaban harus mempertahankan one-based indexing internal, menangani array kosong, posisi tidak valid, dan rentang semi-terbuka, serta tidak pernah mengakses melebihi akhir array.

Menurunkan kompleksitas dan konstruksi

Kandidat harus memberikan biaya kueri, pembaruan, dan seleksi O(log n), konstruksi linear O(n), dan membandingkan batasan array prefix dan segment tree.

Mengenali prasyarat weighted-selection

Jawaban harus mensyaratkan bobot non-negatif dan jumlah kumulatif yang monotonik, kemudian menguji kecocokan tepat, overflow, dan batas angka besar.