Temu duga pengekodan: Melaksanakan modul julat boleh ubah (mutable)

Arahan dan skop

Laksanakan tiga operasi ke atas selang separuh terbuka [left, right): menambah liputan, menguji sama ada kueri diliputi sepenuhnya, dan membuang liputan. Andaikan 1 <= left < right <= 10^9 dan sehingga 10^4 panggilan, sepadan dengan masalah Range Module awam. Nyatakan apa yang berlaku apabila left >= right jika API anda menerima input defensif.

Perkara yang diuji oleh penemu duga

Ujian utama adalah sama ada anda boleh memilih dan mengekalkan invariant struktur data semasa selang disisipkan, dipadamkan dan dikueri. Perwakilan yang dijangkakan ialah koleksi kanonikal yang diisih bagi selang-selang tak bersilang; LeetCode menyenaraikan set tertib (ordered set) dan pokok segmen (segment tree) sebagai pendekatan yang berkaitan. Magicsheet melabelkan masalah ini sebagai sukar (hard) dan menandakannya dengan set tertib dan pokok segmen. Soalan ini juga mendedahkan disiplin sempadan separuh terbuka, keselamatan lelaran (iterator safety), dan perakaunan kekompleksan.

Soalan penjelasan untuk ditanya

1. Adakah titik akhir inklusif? Jawapan ini menggunakan [left, right).
2. Patutkah julat yang bersentuhan seperti [1,3) dan [3,5) digabungkan? Jawapan ini menggabungkannya menjadi satu selang kanonikal.
3. Adakah semua titik akhir diketahui sebelum pelaksanaan? Reka bentuk asas adalah dalam talian (online), jadi ia tidak diketahui.
4. Apakah yang patut dilakukan oleh input left >= right yang tidak sah? Kembali tanpa mengubah keadaan, atau tolaknya secara eksplisit.
5. Adakah domain itu terikat dan cukup statik untuk mewajarkan penggunaan pokok segmen? Itu mempengaruhi reka bentuk alternatif.

Penyelesaian langkah demi langkah

1. Pilih perwakilan dan invariant

Gunakan peta tertib (ordered map) dari permulaan selang ke penghujung. std::map memastikan kunci sentiasa diisih dan mendokumentasikan carian, penyisipan dan pembuangan logaritma; lelaran menaik membolehkan algoritma hanya menelusuri selang yang berdekatan. Normalkan liputan yang bersentuhan, supaya selepas setiap operasi peta tidak mengandungi sepasang dengan previousEnd >= nextStart.

2. Tambah liputan

Mula pada selang pertama yang penghujungnya sekurang-kurangnya left (atau selang pertama selepas pendahulu). Semasa permulaan semasa adalah paling banyak right yang semakin membesar, kembangkan left dan right untuk memasukkan selang tersebut, kemudian tandakannya untuk pemadaman. Padamkan julat bersebelahan yang ditandakan dan masukkan selang yang digabungkan. Keadaan kosong dan julat yang tak bersilang daripada kedua-dua jiran tidak memerlukan struktur khas.

3. Buang liputan dan kueri liputan

Untuk pembuangan, lawati selang dengan start < right dan end > left. Bagi setiap pertindihan, kekalkan [oldStart,left) apabila oldStart < left, dan kekalkan [right,oldEnd) apabila right < oldEnd; padamkan yang asal sebelum memasukkan serpihan. Untuk kueri, periksa selang yang permulaannya merupakan permulaan terbesar yang tidak melebihi left; kembalikan true hanya jika ia wujud dan penghujungnya sekurang-kurangnya right. Dengan titik akhir separuh terbuka, [1,3) tidak meliputi [3,4).

Ketepatan dan kekompleksan

Invariant membuktikan ketepatan melalui induksi. Penambahan menggantikan setiap selang yang disambungkan ke julat baharu dengan kesatuan (union) mereka, jadi tiada titik diliputi yang hilang dan hasilnya adalah kanonikal. Pembuangan menggantikan setiap pertindihan dengan tepat bahagian di luar julat yang dibuang. Mengueri pendahulu adalah mencukupi kerana selang tak bersilang yang diisih memastikan mana-mana selang sebelumnya tidak berakhir lebih lewat, dan mana-mana selang kemudian dengan permulaan yang lebih besar daripada left tidak boleh mengandungi left.

Biar n menjadi bilangan selang yang disimpan dan k bilangan yang disentuh oleh kemas kini. Kueri ialah O(log n). Kemas kini melakukan carian O(log n) ditambah penelusuran lelaran dan pemadaman O(k); pelaksanaan yang mencari semula setiap kunci boleh menjadi O(k log n). Ruang ialah O(n). Pokok segmen adalah munasabah untuk semesta koordinat terikat yang diketahui, manakala pemampatan koordinat memerlukan semua titik akhir di luar talian (offline) dan tidak sesuai untuk panggilan dalam talian sewenang-wenangnya.

Jawapan model

"Saya akan melaksanakan peta tertib yang dinormalkan bagi selang separuh terbuka, diisih, dan tak bersilang. Add mencari dan menggabungkan setiap selang yang bertindih atau bersentuhan, remove memadamkan pertindihan dan mengekalkan paling banyak dua serpihan sempadan, dan query memeriksa pendahulu permulaan yang diminta. Kewajipan bukti utama ialah setiap operasi mengekalkan kesatuan kanonikal. Query berkos O(log n); kemas kini berkos O(log n + k) apabila memadamkan julat lelaran bersebelahan dan menggunakan ruang O(n). Saya akan membandingkan peta dalam talian ini dengan pokok segmen hanya selepas mengesahkan domain koordinat dan sama ada semua titik akhir diketahui."

Kesilapan biasa

• Memperlakukan titik akhir sebagai tertutup → julat bersebelahan kelihatan bertindih secara salah → tentukan [left,right) terlebih dahulu.
• Membiarkan selang yang bersentuhan terpisah → kueri dan kemas kini kemudian menghadapi duplikasi yang boleh dielakkan → normalkan keterdekatan.
• Memadam semasa menambah lelaran yang tidak sah → melangkau nod atau mengakses storan yang telah dibebaskan → simpan lelaran seterusnya atau padamkan julat yang diketahui.
• Memisahkan tanpa mengekalkan kedua-dua belah pihak → liputan hilang pada satu sempadan → uji pembuangan bahagian tengah dan pembendungan penuh.
• Mendakwa setiap kemas kini ialah O(log n) → satu operasi mungkin menyentuh banyak selang → masukkan k dalam batas.
• Menggunakan pemampatan koordinat dalam talian → titik akhir yang belum dilihat membatalkan indeks → gunakan struktur tertib atau bina semula daripada set luar talian yang lengkap.

Susulan dan lanjutan

Kes sempadan manakah yang mesti diuji?

Uji modul kosong, penambahan berulang, kueri tepat pada hujung, penambahan bersentuhan [1,3) kemudian [3,5), pembuangan kepingan tengah, pembuangan yang meliputi keseluruhan selang, pembuangan tanpa pertindihan, julat bersarang, dan titik akhir 0 serta 10^9 apabila API membenarkannya.

Bagaimanakah anda akan menguji invariant tersebut?

Selepas setiap operasi rawak, sahkan (assert) permulaan yang diisih, end > start, dan previousEnd < nextStart. Bandingkan hasil kueri dengan tatasusunan boolean kecil atau model union kekerasan kasar (brute-force) pada domain koordinat yang kecil. Ini menangkap pepijat off-by-one dan kehilangan serpihan.

Bilakah pokok segmen akan menang?

Pilih pokok segmen apabila semesta koordinat terikat atau boleh dimampatkan dan pengagregatan julat atau lazy propagation penting. Ia memberikan operasi logaritma yang boleh diramalkan tetapi menambah kerumitan nod dan keadaan lazy; peta tertib adalah lebih mudah untuk selang jarang (sparse), dalam talian.