Pepohon Fenwick untuk Jumlah Awalan
Kemas kini titik dan buat pertanyaan awalan dalam log n.
Pepohon Fenwick untuk Jumlah Awalan ialah pelajaran Competitive Programming Academy 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 Competitive Programming Academy, dan kemajuan anda disegerakkan merentas web serta aplikasi CoddyKit. Kursus Competitive Programming Academy 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 Python 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
- 30
- Pelajaran
- 120
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 Competitive Programming Academy, tingkat taraf kepada CoddyKit PRO. Kursus Competitive Programming Academy 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 Competitive Programming Academy 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 Competitive Programming Academy?
Tiada pengalaman terdahulu diperlukan. Pembelajaran Competitive Programming Academy 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 Competitive Programming Academy ini?
Ya. Setiap pelajaran Competitive Programming Academy 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