Inversi dengan BIT
Menghitung pasangan yang urutannya terbalik secara efisien
Inversi dengan BIT adalah pelajaran Coding Interview Prep gratis di CoddyKit. Ini adalah pelajaran 2 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 Coding Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Apa Itu Inversi
Inversi adalah pasangan i < j dengan a[i] > a[j]. Inversi merupakan satu pasangan yang berada di luar urutan, dan penghitungannya mengukur seberapa tidak terurutnya sebuah larik.
Mengapa Inversi Penting
Jumlah inversi sama dengan jumlah pertukaran yang dilakukan oleh pengurutan gelembung. Soal-soal kompetitif sering menyembunyikannya dalam pertanyaan tentang peringkat dan ketidakteraturan.
Penghitungan Naif Terlalu Lambat
Memeriksa setiap pasangan memerlukan O(n^2). Untuk n sekitar 100000, terdapat sepuluh miliar pemeriksaan, jauh melampaui batas waktu. Kita memerlukan cara yang lebih cerdas. 🐢
Gagasan BIT
Telusuri dari kiri ke kanan dan tanyakan: berapa banyak elemen sebelumnya yang lebih besar daripada elemen saat ini? Pohon Fenwick menjawabnya selama penelusuran berlangsung.
Menghitung Berdasarkan Frekuensi
BIT menyimpan tabel frekuensi berdasarkan nilai. update(v, 1) mencatat bahwa nilai v telah muncul sejauh ini dalam penelusuran.
update(v, 1)Nilai Lebih Besar Berarti Sufiks
Nilai sebelumnya yang lebih besar daripada v adalah jumlah nilai yang telah dilihat dikurangi jumlah nilai hingga v. Pada elemen ke-i, nilainya adalah i dikurangi query(v).
inv += i - query(v)Kompresi Koordinat
Jika nilainya besar atau negatif, petakan terlebih dahulu ke peringkat 1..n. Kompresi ini membuat BIT tetap kecil tanpa mengubah urutan apa pun.
rank = {v: i for i, v in enumerate(sorted(set(a)), 1)}Penelusuran Lengkap
Telusuri larik, tambahkan setiap jumlah nilai yang lebih besar ke total, lalu masukkan nilai saat ini. Total berjalan tersebut adalah jumlah inversi Anda.
for i, v in enumerate(a):
inv += i - query(rank[v])
update(rank[v], 1)Berjalan dalam n log n
Setiap elemen memicu satu kueri dan satu pembaruan, yang keduanya memerlukan O(log n). Seluruh penghitungan selesai dalam waktu O(n log n). 🚀
Pengurutan Gabung sebagai Kerabat
Pengurutan gabung juga menghitung inversi dalam O(n log n) selama langkah penggabungannya. Versi BIT sering kali lebih singkat untuk ditulis saat berada di bawah tekanan.
Waspadai Luapan Penghitungan
Jumlah inversi dapat mencapai sekitar n kuadrat dibagi dua, yang sangat besar. Bilangan bulat Python tidak terbatas, tetapi dalam bahasa lain Anda memerlukan tipe 64-bit.
Pemeriksaan Singkat
Uji pemahaman Anda tentang biaya penelusuran.
Rangkuman: Menghitung Ketidakteraturan
Anda menghitung inversi dalam O(n log n) dengan menelusuri dari kiri ke kanan dan menanyakan kepada BIT berapa banyak nilai yang lebih besar muncul sebelumnya. Lakukan kompresi nilai jika diperlukan. ✅
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Inversi dengan BIT” gratis?
Ya — teks lengkap “Inversi dengan BIT” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Coding Interview Prep, upgrade ke CoddyKit PRO. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Inversi dengan BIT”?
Menghitung pasangan yang urutannya terbalik secara efisien Kamu berlatih Coding Interview Prep 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 Coding Interview Prep?
Tidak diperlukan pengalaman sebelumnya. Coding Interview Prep 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 2 dari 4.
Berapa lama pelajaran “Inversi dengan BIT” 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 Coding Interview Prep ini?
Ya. Setiap pelajaran Coding Interview Prep 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