Bagaimanakah Anda Melaksanakan Fenwick Tree untuk Dynamic Prefix Sums dan Weighted Selection?

1. Soalan

Anda mempunyai jadual kekerapan dinamik dengan panjang n. Nilai pada kedudukan kerap ditingkatkan, dan sistem mesti menjawab hasil tambah awalan, hasil tambah julat, serta mencari kedudukan yang mengandungi unit berat kumulatif ke-k. Laksanakan Fenwick Tree (Binary Indexed Tree) dengan kemas kini titik dan pertanyaan awalan O(log n), serta bandingkannya dengan tatasusunan awalan biasa dan segment tree.

2. Kekangan dan penjelasan

• Gunakan pengindeksan berasaskan satu secara dalaman; API awam boleh menerima kedudukan berasaskan sifar tetapi mesti menukarnya tepat sekali.
• Kemas kini boleh berupa delta atau perbezaan daripada nilai baharu; nyatakan sama ada nilai negatif dibenarkan.
• Pangkat bermula pada 1. Pemilihan berwajaran hanya ditakrifkan apabila semua berat adalah bukan negatif dan jumlahnya sekurang-kurangnya k.
• Bincangkan struktur satu benang terlebih dahulu; kemas kini serentak memerlukan kunci atau pembahagian (sharding) dan tidak boleh menganggap penulisan integer biasa membentuk snapshot yang konsisten.

3. Idea teras

Entri i menyimpan hasil tambah julat bersebelahan yang panjangnya ialah lowbit(i) = i & -i. Pertanyaan awalan berulang kali menolak lowbit, manakala kemas kini titik berulang kali menambah lowbit, jadi setiap satu menyentuh O(log n) kedudukan tatasusunan. Hasil tambah julat ialah perbezaan dua awalan. Apabila tatasusunan awal diketahui, sebarkan setiap nilai ke indeks induknya untuk membina dalam O(n).

4. Pelaksanaan rujukan

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 pemilihan berwajaran, siasat daripada langkah binari tertinggi. Jika bergerak ke indeks calon mengekalkan hasil tambah kumulatif di bawah k, terima langkah tersebut dan tolak jumlahnya daripada k; indeks akhir ditambah satu ialah kedudukan yang mengandungi pangkat k. Ini memerlukan hasil tambah kumulatif yang monotonik dan oleh itu tidak boleh digunakan secara langsung dengan berat negatif.

5. Kerumitan dan kompromi (trade-offs)

Fenwick Tree menggunakan tatasusunan O(n). Penambahan titik, hasil tambah awalan, dan pemilihan berwajaran adalah O(log n), manakala pembinaan linear adalah O(n). Ia lebih padat dan selalunya mempunyai pemalar yang lebih kecil daripada segment tree, tetapi ia secara semula jadi menyatakan agregat awalan boleh balik dan bukannya minimum julat, kemas kini julat yang kompleks, atau metadata segmen yang kaya. Untuk data baca sahaja, tatasusunan awalan biasa menjawab pertanyaan dalam O(1); Fenwick menjadi bernilai apabila kemas kini kerap berlaku.

6. Pengesahan dan kebolehmerhatian

• Bandingkan setiap add, prefixSum, dan rangeSum dengan tatasusunan naif pada input rawak, termasuk kes kosong, unsur tunggal (singleton), dan indeks terakhir.
• Uji semua sifar, berat yang sangat besar, jumlah yang tepat sama dengan k, k di luar julat, dan indeks tidak sah.
• Buat semakan silang pembinaan linear terhadap penambahan titik berulang dan bandingkan kedua-dua tatasusunan dalaman dan hasil pertanyaan.
• Hasilkan berat rawak bukan negatif untuk pemilihan berwajaran dan semak sempadan awalan bagi setiap k; tolak input berat negatif secara berasingan.

7. Kesilapan lazim

• Mencampurkan indeks berasaskan sifar dan berasaskan satu supaya kedudukan sifar dilangkau atau kedudukan terakhir melimpah (overflow).
• Menganggap i & -i sebagai helah penafian tanpa menerangkan bahawa ia mengekstrak blok binari terendah.
• Menggunakan pemilihan berwajaran dengan nilai negatif walaupun hasil tambah kumulatif tidak lagi monotonik.
• Menulis ganti nod pokok dengan nilai baharu dan bukannya menambah delta di sepanjang laluan kemas kini.

8. Mata pemarkahan temu duga

Menerangkan lowbit dan liputan julat

Calon harus menyatakan julat bersebelahan yang disimpan oleh setiap nod dan sebab pertanyaan serta kemas kini mengikut lompatan lowbit.

Menulis pelaksanaan tanpa ralat sempadan

Jawapan harus mengekalkan pengindeksan berasaskan satu dalaman, mengendalikan tatasusunan kosong, kedudukan tidak sah, dan julat separuh terbuka, serta tidak sekali-kali mengakses melangkaui penghujung tatasusunan.

Menerbitkan kerumitan dan pembinaan

Calon harus memberikan kos pertanyaan, kemas kini dan pemilihan O(log n), pembinaan linear O(n), serta membandingkan sempadan tatasusunan awalan dan segment tree.

Mengenal pasti prasyarat pemilihan berwajaran

Jawapan harus memerlukan berat bukan negatif dan hasil tambah kumulatif yang monotonik, kemudian menguji padanan tepat, limpahan, dan sempadan nombor besar.