Wawancara Koding: Bagaimana Anda menggunakan Li Chao tree untuk kueri minimum garis dinamis?

Masalah dan Konteks

Sebuah layanan daring menerima garis y = m x + b dalam urutan penyisipan arbitrer dan harus mengembalikan nilai minimum pada titik kueri bilangan bulat x. Titik kueri juga bersifat arbitrer. Sebuah ekstensi mungkin membatasi garis pada interval [l, r] atau meminta nilai maksimum sebagai gantinya.

Masalah ini menguji optimasi pemrograman dinamis, invarian divide-and-conquer, dan implementasi segment tree. Jawaban yang kuat pertama-tama menyatakan apakah domain kueri bersifat diskret dan terbatas, lalu menjelaskan mengapa setiap simpul dapat mempertahankan satu garis yang menang di suatu tempat sementara kandidat yang tersisa dikirim ke tepat satu anak simpul.

Apa yang Dinilai oleh Pewawancara

Menurunkan bottleneck dari pemindaian setiap garis dalam O(number_of_lines) per kueri.
Memahami perbandingan titik tengah, penukaran (swap), dan invarian rekursi.
Menangani gradien arbitrer, garis duplikat, koordinat negatif, dan overflow.
Membedakan domain bilangan bulat diskret, domain kontinu, dan garis yang dibatasi segmen.
Memberikan batas penyisipan/kueri O(log C) dan batas penyisipan segmen O(log^2 C).
Menjelaskan kapan gradien monoton dan kueri monoton membuat convex hull trick standar menjadi lebih sederhana.

Klarifikasi yang Perlu Ditanyakan Terlebih Dahulu

Apakah titik kueri berupa bilangan bulat atau riil? Apakah domainnya tetap [L, R] atau diperluas secara dinamis? Ini menentukan kedalaman dan kompresi koordinat.
Apakah operasinya adalah minimum atau maksimum? Apakah himpunan kosong diizinkan, dan nilai sentinel apa yang tidak akan bertabrakan dengan jawaban nyata?
Berapa besaran maksimum gradien, intersep, dan jawaban? Apakah tipe bilangan bulat yang lebih lebar atau perkalian yang diperiksa (checked multiplication) diperlukan?
Apakah garis hanya berlaku pada [l, r]? Penyisipan interval mendistribusikan garis ke beberapa simpul pohon.
Apakah gradien penyisipan atau titik kueri bersifat monoton? Jika ya, convex hull trick berbasis deque mungkin menggunakan konstanta yang lebih kecil.

Kerangka Jawaban 30 Detik

Saya membangun domain segment tree [L, R] dan menyimpan satu garis kandidat di setiap simpul. Saat menyisipkan garis baru, saya membandingkannya dengan garis simpul di titik ujung dan titik tengah. Jika garis baru menang di titik tengah, saya menukarnya ke dalam simpul. Garis yang tergeser masih bisa menang hanya pada setengah bagian kiri atau kanan, jadi saya melakukan rekursi ke salah satu anak simpul. Kueri titik mengevaluasi setiap garis pada jalur dari akar ke daun (root-to-leaf) dan mengambil nilai minimum. Dengan panjang domain C, penyisipan dan kueri adalah O(log C); membatasi garis pada interval membutuhkan biaya O(log^2 C). Kueri maksimum membalikkan pembanding.

Pembahasan Mendalam Langkah demi Langkah

1. Brute Force dan Bottleneck

Simpan daftar garis dan evaluasi setiap m x + b untuk setiap kueri. Ini membutuhkan biaya O(number_of_lines) per kueri. Dalam transisi pemrograman dinamis, penyisipan dan kueri terjadi secara berselang-seling, sehingga baik gradien maupun titik kueri tidak dapat diurutkan tanpa mengubah masalah. Struktur data harus mendistribusikan perbandingan ke seluruh domain nilai.

2. Invarian Simpul

Sebuah simpul mewakili interval tertutup [lo, hi] dan menyimpan garis cur. Di antara garis-garis yang belum didorong ke anak simpul, cur tidak lebih buruk pada setidaknya satu posisi kandidat dalam interval ini. Garis lain yang mungkin masih menjadi optimal hanya dapat melakukannya di anak simpul kiri atau kanan. Pada simpul daun, simpul hanya memerlukan garis yang terbaik pada satu titik.

3. Penukaran Titik Tengah dan Arah Rekursi

Misalkan nw adalah garis baru, cur garis simpul, dan mid titik tengah. Jika nilai garis baru pada mid lebih kecil, tukar keduanya sehingga simpul menyimpan pemenang titik tengah. Setelah penukaran, bandingkan garis mana yang menang pada lo. Jika garis yang tergeser menang di titik ujung kiri, ia mungkin hanya muncul kembali di setengah bagian kiri; jika tidak, bandingkan titik ujung kanan dan lakukan rekursi ke kanan. Selisih dua garis bersifat linear, sehingga urutannya berubah paling banyak satu kali.

text

add(node, lo, hi, nw):
  mid = (lo + hi) // 2
  left = nw(lo) < cur(lo)
  middle = nw(mid) < cur(mid)
  if middle: swap(nw, cur)
  if lo == hi: return
  if left != middle: add(leftChild, lo, mid, nw)
  else: add(rightChild, mid + 1, hi, nw)

Gunakan rumus titik tengah yang aman. Jika m * x + b dapat melebihi rentang 64-bit, gunakan tipe yang lebih lebar, aritmetika yang diperiksa, atau kebijakan saturasi eksplisit.

4. Melakukan Kueri Jalur Root-to-Leaf

Untuk titik x, lakukan rekursi menuju daun yang memuat x, evaluasi garis yang tersimpan pada x di setiap simpul yang dikunjungi, dan kembalikan nilai minimum. Subpohon lain tidak memuat titik tersebut. Pohon implisit hanya mengalokasikan simpul pada jalur yang disentuh oleh penyisipan; simpul kosong mengembalikan sentinel tak hingga positif.

5. Menyisipkan Garis yang Dibatasi pada Interval

Jika garis valid hanya pada [ql, qr], dekomposisikan interval tersebut dengan segment tree standar. Sisipkan garis sekali ke setiap simpul yang tertutup penuh dan lakukan rekursi untuk cakupan parsial. Dekomposisi ini menyentuh O(log C) simpul dan setiap penyisipan Li Chao membutuhkan biaya O(log C), menghasilkan O(log^2 C); kueri titik tetap O(log C).

6. Koordinat Diskret dan Kueri Kontinu

Jika kueri berasal dari himpunan berhingga yang diketahui, urutkan dan hapus duplikat nilai x, lalu gunakan indeksnya sebagai daun. Ini menghindari pembangunan domain kosong yang besar. Untuk kueri bernilai riil, nyatakan presisi dan kondisi berhenti secara eksplisit. Pembuktian domain bilangan bulat tidak secara otomatis berlaku untuk domain kontinu tak terbatas; batasi interval dan tentukan toleransi perbandingan floating-point.

7. Pertukaran (Trade-offs) dan Pengujian

Ketika gradien dan titik kueri keduanya monoton, convex hull trick berbasis deque memiliki konstanta yang lebih kecil. Li Chao lebih tangguh untuk urutan arbitrer, dengan konsekuensi lebih banyak simpul dan rekursi. Uji himpunan kosong, domain satu titik, gradien duplikat, garis identik, koordinat negatif, perpotongan di titik tengah, garis yang menutupi satu titik ujung, hasil kali besar, dan kueri maksimum; bandingkan setiap hasil dengan evaluasi brute-force.

Jawaban Model Berkualitas Tinggi

Pertama-tama saya akan mengonfirmasi apakah domain kueri adalah interval bilangan bulat terbatas atau memerlukan kompresi koordinat. Untuk [L, R], saya membangun Li Chao tree yang simpul-simpulnya menyimpan garis kandidat. Penyisipan membandingkan titik ujung dan titik tengah; pemenang titik tengah tetap berada di simpul, dan garis lainnya berekursi ke salah satu setengah bagian tempat kedua garis dapat berubah urutan. Selisih keduanya bersifat linear, sehingga garis yang tergeser tidak dapat menjadi lebih baik di dua arah yang terpisah. Kueri titik mengambil nilai minimum di sepanjang satu jalur root-to-leaf, memberikan O(log C) untuk penyisipan dan kueri. Jika gradien dan kueri bersifat monoton, saya akan menggunakan convex hull trick; garis yang dibatasi interval memerlukan dekomposisi segmen dan penyisipan O(log^2 C).

Kesalahan Umum

Hanya membandingkan titik tengah lalu berhenti → garis lain mungkin menang di titik ujung → gunakan perbandingan titik ujung dan titik tengah untuk memilih satu anak simpul.
Mengasumsikan gradien harus monoton → penyisipan arbitrer menghasilkan jawaban yang salah → gunakan invarian interval Li Chao atau nyatakan prasyarat convex hull.
Menghitung m * x + b dalam aritmetika 64-bit yang tidak diperiksa → overflow mengubah perbandingan → gunakan aritmetika yang lebih lebar atau yang diperiksa.
Membiarkan domain dinamis tak terbatas → rekursi tidak memiliki terminasi → batasi domain bilangan bulat, kompresi koordinat, atau tentukan presisi floating-point.
Menyalin garis interval ke setiap daun → kompleksitas terdegenerasi → dekomposisikan interval dan sisipkan pada simpul yang tertutup penuh.
Mengembalikan nol untuk simpul kosong → nilai minimum diturunkan secara salah → gunakan sentinel tak hingga positif di luar rentang jawaban.

Pertanyaan Lanjutan dan Tanggapan

Apa yang berubah untuk kueri maksimum?

Balikkan setiap perbandingan, atau negasikan m dan b, selesaikan kueri minimum, lalu negasikan hasilnya. Semantik himpunan kosong dan overflow harus dibalik secara konsisten alih-alih hanya mengubah nilai kembalian akhir.

Bisakah pohon berbasis array menangani domain 10 pangkat 18?

Tidak dengan mengalokasikan setiap simpul di awal. Gunakan pohon implisit yang membuat simpul hanya di sepanjang jalur penyisipan; kedalamannya kira-kira sebesar jumlah bit domain. Jika koordinat kueri berhingga, kompresi koordinat biasanya lebih menghemat memori.

Dua garis seri di titik tengah. Bagaimana Anda menghindari percabangan yang salah?

Pilih aturan penentu seri yang deterministik, seperti mempertahankan garis lama atau memilih urutan gradien. Gunakan pertidaksamaan ketat secara konsisten pada titik ujung dan titik tengah sehingga garis yang identik tidak melakukan rekursi selamanya.

Mengapa satu sisi rekursif saja sudah cukup?

Selisih dua garis bersifat linear dan memiliki paling banyak satu titik nol. Setelah pemenang titik tengah dipertahankan, garis yang tergeser hanya dapat pulih ke arah titik ujung yang urutannya berbeda, sehingga secara unik memilih anak simpul kiri atau kanan.

Kapan convex hull trick lebih baik?

Jika garis tiba dalam urutan gradien monoton dan kueri bersifat monoton, deque hull dapat memberikan kueri O(1) yang diamortisasi atau kueri pencarian biner O(log n) dengan memori lebih sedikit. Urutan arbitrer, atau garis yang dibatasi segmen, lebih diuntungkan oleh keumuman Li Chao.