Gesaan dan konteks
Laksanakan struktur tatasusunan integer dengan sejarah. Setiap kemas kini mengubah satu kedudukan, dan pertanyaan boleh meminta hasil tambah selang tertutup dalam mana-mana versi lama. Versi lama mesti kekal tidak boleh ubah (immutable). Terangkan batasan koordinat, kerumitan masa dan ruang, versi bercabang, dan ujian.
Ini ialah soalan struktur data yang sukar tentang pisah dan takluk (divide-and-conquer), perkongsian struktur, kemas kini tidak boleh ubah, sempadan, dan bukti kerumitan. Andaikan panjang tatasusunan tetap, kemas kini penetapan titik, dan hasil tambah julat selang tertutup [l, r]. Kemas kini julat, pemadaman, atau penggabungan versi adalah lanjutan berasingan dan harus dinyatakan sebelum dilaksanakan.
Perkara yang diuji oleh penemu duga
Penemu duga mahu anda menjelaskan bahawa ketekalan (persistence) membolehkan punca (root) lama terus boleh ditanya; ia tidak menyalin keseluruhan pokok untuk setiap kemas kini. Pelaksanaan yang kukuh mencipta nod baharu di sepanjang laluan kemas kini, menggunakan semula subpokok yang tidak disentuh, dan menyimpan satu punca bagi setiap versi. Ia juga menyatakan konvensyen selang, tingkah laku pertanyaan kosong, penomboran versi, nilai negatif, sempadan, dan had ruang.
Soalan untuk dijelaskan terlebih dahulu
- Adakah panjang tatasusunan dan ruang koordinat tetap, atau bolehkah koordinat dimampatkan terlebih dahulu?
- Adakah kemas kini merupakan penetapan nilai atau penambahan (increment), dan adakah kedudukan yang sama boleh dikemas kini berulang kali?
- Adakah julat tertutup atau separa terbuka, dan apakah yang patut dikembalikan oleh julat kosong?
- Bolehkah versi bercabang daripada mana-mana punca lama, atau hanya menambah daripada versi terkini?
- Adakah keselamatan bebenang (thread safety), ketekalan cakera, atau perkongsian merentas proses diperlukan?
- Adakah kita memerlukan hasil tambah integer yang tepat, pemeriksaan limpahan, atau integer besar (big integers)?
- Apakah had versi dan had jumlah operasi?
Rangka kerja jawapan 30 saat
"Saya akan mewakili setiap versi dengan punca segment tree yang tidak boleh ubah. Kemas kini titik menyalin O(log n) nod dari punca ke daun, berkongsi setiap subpokok adik-beradik yang tidak disentuh, dan pertanyaan menurun dari punca yang diminta, mengembalikan hasil tambah nod untuk liputan penuh. Tatasusunan punca membenarkan percabangan daripada mana-mana versi lama. Pembinaan mengambil O(n); setiap kemas kini dan pertanyaan mengambil O(log n); jumlah ruang adalah pokok awal ditambah O(log n) nod baharu bagi setiap kemas kini. Saya akan menguji cabang, sempadan, nilai negatif, dan kes pembezaan rawak."
Jawapan langkah demi langkah
Nyatakan invariannya terlebih dahulu: nod merangkumi selang tertutup tertentu [lo, hi], sum ialah hasil tambah selang tersebut dalam versinya, daun merangkumi satu kedudukan, hasil tambah dalaman bersamaan dengan hasil tambah anak-anaknya, dan nod tidak pernah dimutasikan selepas penciptaan. Setiap versi menyimpan satu penunjuk punca.
Bagi indeks tatasusunan 0..n-1, bina secara rekursif. Jika input menggunakan koordinat integer yang jarang dan besar, kumpulkan koordinat yang mungkin dan mampatkannya sebelum membina; jangan merealisasikan ruang koordinat yang terlalu besar secara terus.
Pseudokod berikut menggunakan kemas kini penetapan dan pertanyaan selang tertutup:
Node { left, right, sum }
build(lo, hi, values):
if lo == hi: return Node(null, null, values[lo])
mid = floor((lo + hi) / 2)
left = build(lo, mid, values)
right = build(mid + 1, hi, values)
return Node(left, right, left.sum + right.sum)
set(node, lo, hi, index, value):
if lo == hi: return Node(null, null, value)
mid = floor((lo + hi) / 2)
if index <= mid:
nextLeft = set(node.left, lo, mid, index, value)
nextRight = node.right
else:
nextLeft = node.left
nextRight = set(node.right, mid + 1, hi, index, value)
return Node(nextLeft, nextRight, nextLeft.sum + nextRight.sum)
sum(node, lo, hi, ql, qr):
if qr < lo or hi < ql: return 0
if ql <= lo and hi <= qr: return node.sum
mid = floor((lo + hi) / 2)
return sum(node.left, lo, mid, ql, qr)
+ sum(node.right, mid + 1, hi, ql, qr)roots[0] menyimpan pokok awal. Untuk mengemas kini kedudukan i daripada versi base, cipta roots[next] = set(roots[base], 0, n - 1, i, value). Graf versi ialah struktur perkongsian tak berkitar terarah (DAG) yang dirujuk oleh punca, bukan rantai sejarah linear. Percabangan bermaksud memilih mana-mana punca lama sebagai input kemas kini.
Kendalikan sempadan secara eksplisit: untuk n == 0, jangan cipta punca; indeks di luar julat dan ql > qr harus mengembalikan ralat berstruktur atau mematuhi kontrak yang dinyatakan; memotong pertanyaan tidak boleh menyembunyikan ralat pemanggil secara senyap. Elakkan limpahan lo + hi dengan mengira lo + floor((hi - lo) / 2) apabila sempadan integer boleh menjadi besar.
Pembinaan awal menggunakan O(n) nod dan masa. Kemas kini titik menyalin satu laluan punca-ke-daun, jadi ia mencipta O(log n) nod; pertanyaan julat melawat O(log n) segmen kanonikal dan mengambil masa O(log n). Selepas u kemas kini, jumlah ruang ialah O(n + u log n), bukan O(nu). Penetapan atau penambahan julat juga boleh menggunakan penyalinan laluan, tetapi tag malas (lazy tags), gabungan nod, dan batasan ruang akan berubah.
Ketakbolehubahan (immutability) ialah sempadan ketepatan. Jangan sekali-kali mengubah sum atau penunjuk anak bagi nod lama semasa kemas kini. Pemungutan sampah (garbage collection) atau pengiraan rujukan boleh menuntut semula nod; penuntutan semula manual mesti mengetahui punca versi mana yang kekal aktif, kerana memadam satu versi tidak boleh membebaskan nod yang masih dikongsi oleh versi lain.
Jika hanya versi terkini yang penting, segment tree biasa adalah lebih mudah. Ketekalan berbaloi untuk pertanyaan sejarah, pengunduran (rollback), eksperimen percabangan, atau perjalanan masa. Untuk operasi luar talian sepenuhnya, kaedah awalan luar talian atau garisan sapuan (sweep-line) mungkin lebih mudah; kaitkan pilihan struktur data dengan beban kerja pertanyaan.
Mulakan ujian dengan tatasusunan kecil. Selepas setiap kemas kini, salin tatasusunan biasa dan bandingkan versi serta julat rawak dengan struktur tekal. Liputi percabangan dari versi 0, kemas kini berulang pada satu kedudukan, nilai negatif, elemen tunggal, julat penuh, titik tunggal, julat kosong, dan kedua-dua sempadan. Periksa juga perkongsian: selepas mengemas kini satu kedudukan, subpokok yang tidak disentuh harus mengekalkan identiti objek yang sama.
Uji ketakbolehubahan secara langsung. Simpan semua keputusan pertanyaan versi lama, lakukan beberapa kemas kini percabangan, dan tanya punca lama sekali lagi; sebarang perubahan bermakna nod lama telah dimutasikan. Untuk beban kerja yang besar, kira nod yang diperuntukkan dan sahkan pertumbuhan mendekati O(n) awal ditambah O(log n) setiap kemas kini dan bukannya salinan keseluruhan pokok secara tidak sengaja.
Contoh jawapan berkualiti tinggi
"Saya akan mengandaikan tatasusunan dengan panjang tetap, kemas kini penetapan titik, hasil tambah selang tertutup, dan percabangan daripada mana-mana versi lama. Setiap nod merangkumi [lo, hi] dan menyimpan hasil tambahnya; nod adalah tidak boleh ubah selepas pembinaan. roots[v] menyimpan punca bagi versi v.
Bina secara rekursif. Semasa kemas kini, salin laluan ke daun sasaran: cipta anak baharu di bahagian sasaran, gunakan semula penunjuk lama di bahagian satu lagi, dan cipta setiap induk baharu daripada hasil tambah anak-anaknya. Buat pertanyaan dari punca yang diminta; kembalikan sifar jika tiada pertindihan, hasil tambah nod untuk liputan penuh, dan lakukan rekursi untuk keadaan lain.
Pembinaan mengambil masa dan ruang O(n). Setiap kemas kini mencipta O(log n) nod, dan kedua-dua kemas kini serta pertanyaan mengambil O(log n); selepas u kemas kini, jumlah ruang ialah O(n + u log n). Punca lama masih menunjuk kepada nod lama, jadi versi sejarah tidak boleh dicemari. Mampatkan ruang koordinat yang besar terlebih dahulu; untuk kemas kini julat, nilai semula tag malas dan ruang.
Saya akan menguji cabang daripada versi 0, kemas kini berulang, nilai negatif, julat kosong, dan setiap sempadan terhadap oracle tatasusunan biasa. Saya akan mengesahkan bahawa subpokok yang tidak disentuh dikongsi dan pertanyaan lama kekal tidak berubah selepas kemas kini baharu. Jika hanya nilai terbaharu yang diperlukan, saya akan menggunakan segment tree biasa dan hanya memilih ketekalan apabila sejarah atau pengunduran adalah keperluan sebenar."
Kesilapan biasa
- Menyalin keseluruhan pokok → setiap kemas kini menjadi ruang O(n) → salin hanya laluan punca-ke-daun.
- Memutasikan nod lama dan menyimpan punca baharu → setiap versi lama yang berkongsi dengannya akan berubah → pastikan nod kekal tidak boleh ubah.
- Menganggap versi sebagai satu rantai linear → anda tidak boleh bereksperimen atau berundur dari punca sebarangan → benarkan tatasusunan punca bercabang.
- Membiarkan konvensyen selang tersirat → julat tertutup dan separa terbuka menghasilkan pepijat sempadan → tetapkan satu konvensyen dalam invarian dan tandatangan.
- Merealisasikan koordinat yang besar secara langsung → ruang koordinat boleh mengatasi bilangan titik sebenar → mampatkan koordinat atau gunakan nod dinamik.
- Mendakwa jumlah ruang O(n) → setiap kemas kini menambah nod laluan → nyatakan O(n + u log n).
- Membebaskan nod secara rekursif apabila memadam versi → versi lain mungkin masih berkongsi nod tersebut → gunakan pengiraan rujukan atau pemungutan sampah.
Soalan susulan dan jawapan
Soalan susulan 1: Adakah struktur ini masih berfungsi untuk penambahan julat (range addition)?
Salin laluan nod yang disentuh oleh kemas kini dan salin setiap laluan yang berkaitan. Jika tag malas digunakan, tag tersebut kepunyaan nod baharu dan tidak boleh ditulis ke dalam nod yang dikongsi. Bilangan nod baharu boleh berkisar daripada O(log n) hingga O(log n ditambah nod yang diliputi), jadi berikan batasan untuk pelaksanaan sebenar dan bukannya menggunakan semula dakwaan kemas kini titik.
Soalan susulan 2: Bagaimanakah anda membuat pertanyaan bagi perbezaan antara dua versi?
Rentasi kedua-dua punca bersama-sama. Jika penunjuk nod adalah sama, subpokok tersebut tidak berubah dan boleh dilangkau. Jika tidak, turun ke bawah atau kira perbezaan agregat. Melaporkan setiap kedudukan yang diubah juga bergantung pada saiz output.
Soalan susulan 3: Mengapa tidak menyalin tatasusunan dan membina hasil tambah awalan (prefix sum) setiap kali?
Menyalin tatasusunan menelan O(n) masa dan ruang bagi setiap kemas kini. Dengan versi yang sedikit dan tatasusunan yang kecil, kaedah yang lebih mudah itu mungkin lebih baik; ketekalan mengorbankan O(log n) ruang baharu demi membolehkan banyak versi, pertanyaan sejarah dalam talian, dan kemas kini tempatan.
Soalan susulan 4: Bagaimanakah anda mengekalkan punca versi ke cakera secara persisten?
Berikan ID yang stabil kepada nod, simpan ID anak dan bukannya penunjuk memori, dan kekalkan jadual versi-ke-punca. Gunakan penambahan (append) atau salin-atas-tulis (copy-on-write) dan pastikan nod baharu adalah tahan lasak (durable) sebelum menerbitkan punca. Semasa pemulihan, sahkan rujukan dan jadual punca; jangan sesekali mensirikan alamat memori mentah.
Soalan susulan 5: Bagaimanakah anda membuktikan bahawa versi lama tidak dicemari?
Gunakan induksi ke atas kemas kini: hanya nod baharu dicipta, tiada medan nod lama yang berubah, dan pokok baharu merujuk kepada subpokok lama yang tidak disentuh serta laluan baharu. Oleh itu, nod yang boleh dicapai daripada punca lama dan nilainya kekal tidak berubah. Ujian pembezaan percabangan rawak mengesahkan invarian ini dalam amalan.