Temu duga pengekodan: Bagaimanakah anda menggunakan wavelet matrix untuk pertanyaan julat ke-k?

Prompt dan skop

Diberikan array integer statik a, jawab banyak pertanyaan julat separuh terbuka [l, r): kembalikan nilai terkecil ke-k, kekerapan x, dan bilangan elemen dalam [lo, hi). Array tidak pernah berubah dan nilainya mungkin besar. Reka bentuk dan analisis struktur yang lebih pantas daripada mengisih setiap julat.

Wavelet matrix mempartisi nilai secara stabil mengikut bit dari yang paling signifikan hingga yang paling kurang signifikan, menyimpan bitvector dan kiraan prefix-one pada setiap tahap. Ia tidak memerlukan penunjuk pepohon yang eksplisit; setiap pertanyaan memetakan intervalnya ke tahap seterusnya. Nyatakan bahawa k adalah berasaskan sifar (zero-based), kendalikan pemampatan koordinat dan duplikasi, serta berikan batasannya.

Perkara yang dinilai oleh penemu duga

• Terangkan sebab pemetakan stabil, permulaan blok sifar dan pemetaan rank mengekalkan susunan.
• Pilih nilai ke-k pada [l, r) dan kumpul bit dengan betul.
• Kendalikan duplikasi, julat kosong, k di luar julat dan nilai bertanda (signed).
• Bezakan laluan untuk kiraan domain nilai, kekerapan titik dan pertanyaan ke-k.
• Berikan batas pertanyaan O(B), pembinaan O(nB) dan ruang yang boleh dimampatkan.
• Kenal pasti bahawa struktur statik tidak menyediakan kemas kini yang murah dan ketahui alternatifnya.

Soalan penjelasan

1. Adakah r eksklusif, dan adakah k berasaskan sifar atau berasaskan satu?
2. Adakah array benar-benar immutable? Jika tidak, apakah kadar kemas kini dan pertanyaan?
3. Adakah nilai bertanda, dan apakah lebar bit maksimumnya? Bolehkah kita melakukan pemampatan koordinat padanya?
4. Berapakah memori yang tersedia untuk rank, dan adakah bitvector boleh disekat (blocked) atau dimampatkan?
5. Adakah kita hanya memerlukan ke-k, atau juga kekerapan, pendahulu (predecessor), atau hasil tambah julat (range sum)? Operasi ini mempengaruhi pilihan.

Jawapan 30 saat

Saya akan memampatkan koordinat nilai kepada kod bukan negatif dengan lebar bit B. Semasa pembinaan, partisi jujukan semasa secara stabil dari bit tertinggi ke bawah, menyimpan bitvector setiap tahap dan kiraan prefix rank-one. Untuk ke-k, simpan [l,r), kira sifar pada tahap tersebut, dan sama ada petakan ke blok sifar atau tolak sifar dan petakan ke blok satu sambil menetapkan bit jawapan tersebut. Kekerapan menggunakan dua traversal rank; kiraan domain nilai ialah perbezaan dua panggilan countLess. Kos pertanyaan ialah O(B) dan kos pembinaan ialah O(nB).

Penyelesaian langkah demi langkah

1. Enkod domain nilai

Untuk integer bertanda sewenang-wenangnya, susun nilai-nilai unik dan petakannya kepada 0..m-1, mengekalkan array kod-ke-nilai. Kemudian B ialah ceil(log2(m)), dengan kes eksplisit untuk m=1. Jika susunan semula jadi mesti dikekalkan secara langsung, terbalikkan bit tanda sebelum menganggap nilai bertanda sebagai tidak bertanda (unsigned).

2. Bina satu tahap yang stabil

Periksa cur pada bit, tambahkan semua nilai bit sifar ke next, kemudian semua nilai bit satu, mengekalkan susunan dalam kedua-dua kumpulan. bv[i] merekodkan bit pada kedudukan asal i, dan zeroCount ialah bilangan sifar. Kestabilan memastikan interval kemudiannya terikat kepada elemen asal yang sama.

rank1(i) = number of ones in bv[0..i)
zeroCount = n - rank1(n)
for interval [l, r):
  zero interval = [l - rank1(l), r - rank1(r))
  one interval  = [zeroCount + rank1(l), zeroCount + rank1(r))

3. Buat pertanyaan nilai julat ke-k

Pada setiap tahap kira zeros = (r-l) - (rank1(r)-rank1(l)). Apabila k lebih kecil daripada sifar, petakan ke interval sifar. Jika tidak, tolak sifar, petakan ke interval satu, dan tetapkan bit jawapan semasa. Selepas B tahap, nyahkod kod kembali ke nilai asalnya.

4. Buat pertanyaan kekerapan satu nilai

Anggap setiap bit sasaran sebagai cabang tetap dan petakan [l,r) dengan cara yang sama. Sasaran sifar mengikut interval sifar; sasaran satu mengikut interval satu menggunakan zeroCount. Selepas B tahap, panjang interval ialah kekerapannya. Sasaran yang tiada dalam kamus termampat mengembalikan sifar.

5. Buat pertanyaan julat nilai

Takrifkan countLess(x, l, r) sebagai bilangan nilai di bawah x dalam [l,r). Pada tahap di mana x mempunyai bit satu, setiap cabang sifar adalah lebih kecil, jadi tambahkan zeros dan teruskan ke dalam cabang satu. Untuk bit sifar, teruskan hanya ke dalam cabang sifar. Bilangan dalam [lo, hi) ialah countLess(hi)-countLess(lo).

6. Batasan dan pengesahan

Takrifkan tingkah laku untuk julat kosong atau apabila titik akhir kiri tidak lebih kecil daripada titik akhir kanan; jangan sekali-kali mengindeks array rank di luar batasannya. Wajibkan k berada dalam panjang julat semasa. Uji semua kes sama, diisih, duplikasi berselang-seli, nilai negatif, julat satu elemen, lebar bit maksimum, dan nilai yang tiada dalam kamus, membandingkan setiap hasil dengan isihan atau kiraan brute-force.

7. Kekompleksan dan pertukaran (trade-offs)

Dengan kiraan awalan biasa, setiap tahap menyimpan O(n) pembilang, jadi ruang dan pembinaan ialah O(nB) dan setiap operasi ialah O(B). Bitvector termampat yang menyokong rank mengurangkan ruang dan pemalar. Struktur ini sesuai untuk beban kerja yang tidak boleh diubah dan sarat dengan pertanyaan. Untuk kemas kini, pertimbangkan pembinaan semula secara blok, bitvector dinamik, segment tree bagi set bertertib, atau pemprosesan luar talian dan nilai semula kos memori serta kemas kini.

Contoh jawapan yang mantap

Saya akan menyatakan bahawa julat adalah separuh terbuka, k adalah berasaskan sifar, dan array adalah immutable. Saya akan memampatkan koordinat nilai dan menggunakan B bit. Pembinaan mempartisi secara stabil dari bit tertinggi ke bawah, mengekalkan kiraan prefix rank-one dan panjang blok sifar pada setiap tahap.

Untuk ke-k, setiap tahap mengira sifar dalam interval semasa. Jika k tergolong dalam sifar, petakan dengan l-rank1(l) dan r-rank1(r); jika tidak, tolak sifar, petakan dengan zeroCount+rank1(l) dan zeroCount+rank1(r), serta tetapkan bit jawapan. Kekerapan mengikut laluan nilai tetap, manakala bilangan domain nilai ialah dua panggilan countLess. Pembinaan ialah O(nB) dan setiap pertanyaan O(B), dengan ralat eksplisit atau sifar untuk julat tidak sah dan kod yang tiada.

Kesilapan lazim

• Mencampurkan julat tertutup dan separuh terbuka → rank beralih sebanyak satu → gunakan [l,r) secara konsisten dan tulis pemetaannya.
• Terlupa partisi stabil → interval seterusnya tidak lagi mengenal pasti elemen yang sama → kekalkan susunan dalam kedua-dua blok.
• Memasuki blok satu tanpa menolak sifar → nilai ke-k menjadi terlalu besar → tolak sebelum memetakan.
• Membandingkan nilai bertanda sebagai bit tidak bertanda → nilai negatif tersalah susun → mampatkan atau terbalikkan bit tanda.
• Menganggap kemas kini adalah murah → kemas kini membatalkan pilih atur tahap → nyatakan prasyarat statik dan alternatifnya.
• Menguji nilai unik sahaja → pepijat duplikasi dan batasan kekal tersembunyi → uji kes sama, berselang-seli, kosong dan tidak sah.

Soalan susulan dan respons

Mengapa tidak mengisih setiap julat?

Mengisih satu julat menelan kos O((r-l) log(r-l)) dan mengulangi kerja merentasi pertanyaan. Matriks mempra-hitung maklumat percabangan, jadi pertanyaan hanya melawat B tahap dan sesuai untuk beban kerja statik dengan pertanyaan tinggi.

Mengapakah rank1 memetakan interval?

Prefix rank memberitahu berapa banyak angka satu berlaku sebelum setiap titik akhir, yang memberikan kedudukan relatif interval dalam blok sifar dan satu. Pempartisian stabil memastikan kedudukan tersebut mewakili elemen yang sama.

Bagaimanakah anda menjawab k-th terbesar?

Tukarkannya kepada k-th terkecil dengan length - 1 - k, atau utamakan cabang satu pada setiap tahap sambil menolak bilangannya. Kedua-duanya kekal O(B).

Bagaimana jika domain nilai jauh lebih besar daripada n?

Mampatkan koordinat nilai yang diperhatikan dan simpan peta songsang. Untuk nilai pertanyaan yang tidak kelihatan, lakukan carian binari pada sempadan sisipannya atau kembalikan kekerapan sifar.

Bagaimana jika kemas kini diperlukan?

Wavelet matrix biasa tidak mesra kemas kini. Gunakan pembinaan semula secara blok, bitvector dinamik, segment tree bagi struktur bertertib, atau pemprosesan luar talian berdasarkan nisbah kemas kini/pertanyaan, sasaran kependaman dan memori.