Fenwick Tree untuk Jumlah Awalan
Pembaruan titik dan query awalan dalam log n
Fenwick Tree untuk Jumlah Awalan adalah pelajaran Competitive Programming Academy gratis di CoddyKit. Ini adalah pelajaran 1 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar Competitive Programming Academy, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Competitive Programming Academy mencakup 4 pelajaran total.
Mengapa Larik Awalan Tidak Berhasil
Larik jumlah awalan biasa dapat menjawab rentang secara langsung, tetapi satu pembaruan saja memaksa Anda membangunnya kembali. Jika pembaruan dilakukan berkali-kali, prosesnya menjadi lambat. ⏱️
Memperkenalkan Pohon Fenwick
Pohon Fenwick, atau BIT, mendukung pembaruan titik dan kueri awalan dalam O(log n). Struktur ini menjadi pilihan utama Anda untuk total berjalan yang dinamis.
Dirancang dengan Indeks Mulai dari Satu
Pohon Fenwick berada dalam larik dengan indeks mulai dari 1. Kita menggunakan indeks 0 sebagai penanda yang tidak digunakan, sehingga semua data nyata Anda dimulai pada posisi 1.
tree = [0] * (n + 1)Keajaiban Bit Terendah yang Bernilai Satu
Setiap indeks mencakup satu blok nilai. Ukuran blok tersebut sama dengan i & -i, yaitu bit bernilai satu terendah dari i. Satu trik ini menjadi dasar kerja seluruh pohon.
lowbit = i & -iMemperbarui Satu Titik
Untuk menambahkan nilai pada posisi i, lompat maju sebesar lowbit pada setiap langkah, dengan menyentuh setiap blok yang memuat i.
while i <= n:
tree[i] += delta
i += i & -iMengkueri Jumlah Awalan
Untuk menjumlahkan i nilai pertama, berjalanlah mundur dengan mengurangi lowbit pada setiap langkah hingga mencapai nol.
s = 0
while i > 0:
s += tree[i]
i -= i & -iKedua Perulangan Bersifat Logaritmik
Setiap perulangan mematikan satu bit pada setiap iterasi, sehingga berjalan paling banyak log n kali. Itulah alasan pembaruan dan kueri tetap cepat.
Jumlah Rentang dari Dua Awalan
Ingin mendapatkan jumlah dari l hingga r? Ambil prefix(r) minus prefix(l-1), seperti pada larik awalan statis, tetapi kini pembaruan juga murah.
range_sum = query(r) - query(l - 1)Membangun Pohon
Pembangunan paling sederhana cukup memanggil update untuk setiap nilai awal. Proses ini memerlukan O(n log n) dan cukup cepat untuk sebagian besar kompetisi.
for i, v in enumerate(a, 1):
update(i, v)Penggunaan Memori yang Sangat Kecil
Pohon Fenwick hanya memerlukan satu larik berukuran n+1. Jejak memori yang ringkas itu adalah salah satu alasan struktur ini sangat disukai dalam kompetisi. 💾
Kapan Memilih BIT
Pilih pohon Fenwick ketika Anda menyelingi pembaruan titik dengan kueri jumlah awalan atau rentang. Struktur ini singkat untuk ditulis dan sulit dikalahkan.
Pemeriksaan Singkat
Mari pastikan Anda memahami cara perulangan bergerak.
Rangkuman: Dasar-Dasar BIT
Anda telah mengenal pohon Fenwick: berindeks mulai dari 1, didukung oleh i & -i, dengan pembaruan titik dan kueri awalan yang keduanya berjalan dalam O(log n). Berikutnya, kita akan menggunakannya untuk menghitung inversi. 🎯
Belajar Python dengan tutor AI — gratis
Tulis dan jalankan kode asli di browser kamu, dapatkan bantuan instan dari tutor AI 24/7, dan lanjutkan di mana kamu tinggalkan di web atau aplikasi.
- Kursus
- 30
- Pelajaran
- 120
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Fenwick Tree untuk Jumlah Awalan” gratis?
Ya — teks lengkap “Fenwick Tree untuk Jumlah Awalan” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Competitive Programming Academy, upgrade ke CoddyKit PRO. Kursus Competitive Programming Academy mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Fenwick Tree untuk Jumlah Awalan”?
Pembaruan titik dan query awalan dalam log n Kamu berlatih Competitive Programming Academy dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.
Apakah aku perlu pengalaman untuk memulai Competitive Programming Academy?
Tidak diperlukan pengalaman sebelumnya. Competitive Programming Academy di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 1 dari 4.
Berapa lama pelajaran “Fenwick Tree untuk Jumlah Awalan” memakan waktu?
Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.
Bisakah aku menulis dan menjalankan kode dalam pelajaran Competitive Programming Academy ini?
Ya. Setiap pelajaran Competitive Programming Academy menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.
Semua pelajaran dalam kursus ini
- Fenwick Tree untuk Jumlah Awalan
- Inversi dengan BIT
- Segment Tree: Membangun & Melakukan Query
- Propagasi Malas untuk Pembaruan Rentang