Pepohon Fenwick untuk Jumlah Awalan
Kemas kini titik dan buat pertanyaan awalan dalam log n.
Pepohon Fenwick untuk Jumlah Awalan ialah pelajaran Persediaan Temu Duga Pengaturcaraan percuma di CoddyKit. Ini ialah pelajaran 1 daripada 4. Anda boleh membaca keseluruhan pelajaran di bawah secara percuma — kemudian berlatih secara praktikal dalam pelayar menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7. Pelajaran ini merupakan sebahagian daripada laluan pembelajaran Persediaan Temu Duga Pengaturcaraan, dan kemajuan anda disegerakkan merentas web serta aplikasi CoddyKit. Kursus Persediaan Temu Duga Pengaturcaraan merangkumi sejumlah 4 pelajaran.
Mengapa Tatasusunan Awalan Gagal
Tatasusunan jumlah awalan biasa menjawab julat serta-merta, tetapi satu kemas kini sahaja memaksa anda membinanya semula. Dengan banyak kemas kini, proses itu menjadi perlahan. ⏱️
Memperkenalkan Pepohon Fenwick
Pepohon Fenwick, atau BIT, menyokong kemas kini titik dan pertanyaan awalan dalam O(log n). Ia ialah pilihan utama anda untuk jumlah berjalan yang dinamik.
Berindeks Satu Mengikut Reka Bentuk
Pepohon Fenwick berada dalam tatasusunan berindeks satu. Kami menggunakan indeks 0 sebagai penanda senyap, jadi semua data sebenar anda bermula pada kedudukan 1.
tree = [0] * (n + 1)Keajaiban Bit Terendah yang Ditetapkan
Setiap indeks meliputi satu blok nilai. Saiz blok itu sama dengan i & -i, iaitu bit terendah yang ditetapkan bagi i. Satu helah ini menggerakkan seluruh pepohon.
lowbit = i & -iMengemas Kini Satu Titik
Untuk menambah nilai pada kedudukan i, lompat ke hadapan mengikut bit terendah pada setiap langkah dan sentuh setiap blok yang mengandungi i.
while i <= n:
tree[i] += delta
i += i & -iMenyoal Jumlah Awalan
Untuk menjumlahkan i nilai pertama, bergerak ke belakang sambil menolak bit terendah pada setiap langkah sehingga mencapai sifar.
s = 0
while i > 0:
s += tree[i]
i -= i & -iKedua-dua Gelung Bersifat Logaritma
Setiap gelung memadam satu bit pada setiap lelaran, jadi gelung itu berjalan paling banyak log n kali. Itulah sebabnya kemas kini dan pertanyaan kekal pantas.
Jumlah Julat daripada Dua Jumlah Awalan
Mahukan jumlah dari l hingga r? Ambil jumlah awalan hingga r tolak jumlah awalan hingga l-1, sama seperti tatasusunan awalan statik, tetapi kini kemas kini juga murah.
range_sum = query(r) - query(l - 1)Membina Pepohon
Pembinaan paling mudah hanya melakukan kemas kini bagi setiap nilai permulaan. Proses ini ialah O(n log n) dan cukup pantas untuk kebanyakan pertandingan.
for i, v in enumerate(a, 1):
update(i, v)Jejak Memori yang Kecil
Pepohon Fenwick hanya memerlukan satu tatasusunan bersaiz n+1. Jejak yang padat itu merupakan salah satu sebab pepohon ini sangat disukai dalam pertandingan. 💾
Bila Perlu Menggunakan BIT
Pilih pepohon Fenwick apabila anda menyelang-selikan kemas kini titik dengan pertanyaan jumlah awalan atau jumlah julat. Kodnya ringkas dan sukar ditandingi.
Semakan Pantas
Mari kukuhkan pemahaman tentang pergerakan gelung.
Imbas Kembali: Asas BIT
Anda telah mengenali pepohon Fenwick: berindeks satu, digerakkan oleh i & -i, dengan kemas kini titik dan pertanyaan awalan yang kedua-duanya dalam O(log n). Seterusnya, kita menggunakannya untuk mengira penyongsangan. 🎯
Pelajari Persediaan Temu Duga Pengaturcaraan dengan tutor kecerdasan buatan — percuma
Tulis dan jalankan kod sebenar dalam pelayar anda, dapatkan bantuan segera daripada tutor kecerdasan buatan yang tersedia 24/7, dan sambung semula dari tempat anda berhenti di web atau dalam aplikasi.
- Kursus
- 90
- Pelajaran
- 360
Soalan Lazim
Adakah pelajaran “Pepohon Fenwick untuk Jumlah Awalan” percuma?
Ya — teks penuh “Pepohon Fenwick untuk Jumlah Awalan” boleh dibaca secara percuma di web ini. Untuk berlatih secara interaktif menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7, serta membuka kunci baki kursus Persediaan Temu Duga Pengaturcaraan, tingkat taraf kepada CoddyKit PRO. Kursus Persediaan Temu Duga Pengaturcaraan merangkumi sejumlah 4 pelajaran.
Apakah yang akan saya pelajari dalam “Pepohon Fenwick untuk Jumlah Awalan”?
Kemas kini titik dan buat pertanyaan awalan dalam log n. Anda berlatih Persediaan Temu Duga Pengaturcaraan menggunakan kod praktikal yang dijalankan terus dalam pelayar, manakala tutor kecerdasan buatan 24/7 menjawab soalan anda semasa anda mengikuti pelajaran.
Adakah saya memerlukan pengalaman untuk memulakan Persediaan Temu Duga Pengaturcaraan?
Tiada pengalaman terdahulu diperlukan. Pembelajaran Persediaan Temu Duga Pengaturcaraan di CoddyKit disusun untuk pelajar daripada peringkat pemula hingga lanjutan, jadi anda boleh bermula di sini atau dari awal dan belajar mengikut kadar anda sendiri. Ini ialah pelajaran 1 daripada 4.
Berapa lamakah pelajaran “Pepohon Fenwick untuk Jumlah Awalan” diambil?
Kebanyakan pelajaran CoddyKit mengambil masa kira-kira 5–10 minit. Setiap pelajaran ringkas dan interaktif, jadi anda boleh membuat kemajuan secara berterusan dan menyambung tepat dari tempat anda berhenti di web atau aplikasi.
Bolehkah saya menulis dan menjalankan kod dalam pelajaran Persediaan Temu Duga Pengaturcaraan ini?
Ya. Setiap pelajaran Persediaan Temu Duga Pengaturcaraan menyertakan penyunting kod terbina dalam, jadi anda boleh menulis dan menjalankan kod sebenar terus dalam pelayar serta menerima maklum balas kecerdasan buatan serta-merta — tanpa memerlukan persediaan setempat.
Semua pelajaran dalam kursus ini
- Pepohon Fenwick untuk Jumlah Awalan
- Songsangan dengan BIT
- Pepohon Segmen: Bina dan Pertanyaan
- Penyebaran Malas untuk Kemas Kini Julat