Temu Duga Pengekodan: Bagaimanakah anda membina lazy segment tree untuk penambahan julat (range add) dan hasil tambah julat (range sum)?

Kehendak soalan dan skop

Diberikan satu tatasusunan integer dengan panjang n, proses dua operasi dalam talian: tambah delta kepada setiap nilai dalam selang tertutup [l, r], dan kembalikan hasil tambah bagi [l, r]. Sasarkan pembinaan O(n), O(log n) bagi setiap operasi, dan ruang tambahan O(n). Nyatakan bahawa selang adalah tertutup, delta mungkin bernilai negatif, dan ketekalan (persistence) berada di luar skop melainkan diminta.

Perkara yang diuji oleh penemu duga

Tuliskan invariant terlebih dahulu: tree[p] sentiasa merupakan hasil tambah sebenar bagi selang nod, manakala lazy[p] ialah tokokan seragam yang sudah disertakan dalam hasil tambah tersebut tetapi belum digunakan pada nod anak. Jawapan yang kukuh hanya mengemas kini nod yang diliputi sepenuhnya, menolak (push) sebelum traversal separa, dan mendarab tokokan dengan panjang yang diliputi.

Penjelasan sebelum mengekod

1. Adakah kemas kini berbentuk penambahan, penetapan nilai (assignment), atau nilai minimum julat? Peraturan komposisi lazy-tag masing-masing berbeza.
2. Adakah agregat merupakan hasil tambah, minimum, atau maksimum? Percantuman nod dan formula tag akan berubah.
3. Adakah selang tertutup? Jawapan ini menggunakan [l, r] tertutup; selang separuh terbuka memerlukan pemisahan dan panjang yang konsisten.
4. Sejauh manakah nilai boleh menjadi besar? tree[p] + delta * length mungkin melimpah (overflow) pada integer 32-bit, jadi pilih jenis data yang lebih luas.

Penyelesaian dan penerbitan yang disyorkan

Simpan pokok binari tersirat dalam tatasusunan. Nod [lo, hi] berpecah pada mid kepada [lo, mid] dan [mid+1, hi]. Bagi kemas kini yang diliputi sepenuhnya, tambah delta * (hi-lo+1) kepada tree[p] dan kumpulkan delta dalam lazy[p]; nilai anak boleh dibiarkan tidak disentuh sehingga diperlukan.

class LazySumTree:
    def __init__(self, values):
        self.n = len(values)
        self.tree = [0] * (4 * max(1, self.n))
        self.lazy = [0] * len(self.tree)
        if self.n:
            self._build(1, 0, self.n - 1, values)

    def _apply(self, p, lo, hi, delta):
        self.tree[p] += delta * (hi - lo + 1)
        self.lazy[p] += delta

    def _push(self, p, lo, hi):
        if self.lazy[p] == 0 or lo == hi:
            return
        mid = (lo + hi) // 2
        d = self.lazy[p]
        self._apply(p * 2, lo, mid, d)
        self._apply(p * 2 + 1, mid + 1, hi, d)
        self.lazy[p] = 0

Lengkapkan add dan sum secara rekursif dengan invariant yang sama: panggil _apply pada liputan penuh; panggil _push sebelum liputan separa; kira semula nod induk daripada anak-anaknya selepas kembali. Setiap peringkat hanya melawat bilangan nod sempadan yang malar, jadi kemas kini dan pertanyaan adalah O(log n) dan storan adalah O(n).

Alternatif dan pertukaran kompromi (trade-offs)

Bagi kemas kini titik bersama hasil tambah awalan, Fenwick tree adalah lebih pendek dan mempunyai pemalar yang lebih kecil. Bagi penambahan julat luar talian yang diikuti oleh satu bacaan akhir, tatasusunan perbezaan adalah lebih mudah. Lazy segment tree berbaloi dengan kekompleksannya apabila kemas kini julat dalam talian dan pengagregatan julat wujud bersama. Penetapan julat (range assignment) memerlukan tag "has assignment" tambahan dan peraturan keutamaan yang jelas: penetapan menggantikan penetapan dan tag penambahan yang lebih lama, manakala penambahan terkemudian dikumpulkan selepasnya.

Mod kegagalan, sempadan, dan contoh lawan

• Terlupa panjang selang menyebabkan penambahan 3 kepada [2, 5] meningkatkan hasil tambah sebanyak 3 dan bukannya 12.
• Melakukan rekursi selepas liputan penuh kehilangan lazy propagation dan mungkin menggunakan kemas kini secara berulang kali.
• Kegagalan membersihkan tag selepas proses push akan menggunakan tokokan yang sama sekali lagi pada lawatan seterusnya.
• Tidak mengira semula induk selepas kemas kini separa menyebabkan pertanyaan liputan penuh yang berikutnya lapuk (stale).
• Mencampurkan selang tertutup dan separuh terbuka menyebabkan ralat satu elemen atau mid+1; sahkan tatasusunan kosong, l > r, dan n=0 pada sempadan.

Senarai semak ujian dan pengesahan

Gunakan tatasusunan naif sebagai orakel, jana kemas kini dan pertanyaan rawak, serta bandingkan selepas setiap operasi. Sertakan julat satu elemen, julat penuh, kedua-dua sempadan, delta negatif, pertindihan berulang, dan nilai yang semuanya sama. Sahkan (assert) bahawa induk bersamaan dengan hasil tambah anak-anaknya selepas panggilan rekursif, dan periksa bahawa jenis integer yang dipilih tidak melimpah pada input yang besar. Tambahkan ujian kesetaraan jika melaksanakan susun atur lelaran (iterative).

Soalan susulan

Bagaimanakah range assignment dan range add boleh wujud bersama?

Simpan tag assignment pilihan dan tag add bagi setiap nod. Assignment baharu menggantikan kedua-dua assignment dan tag add yang lebih lama; add baharu terkumpul selepas assignment tersebut. Lakukan push pada assignment dahulu dan add kedua. Susunan tersebut merupakan peraturan ketepatannya.

Bagaimanakah anda menyokong nilai minimum julat?

Simpan nilai minimum selang dan bukannya hasil tambah; penambahan julat masih menambah delta kepada nilai minimum tersebut, jadi tag malas kekal mudah. Julat chmin atau chmax memerlukan invariant yang lebih kaya seperti segment-tree beats.

Bagaimanakah anda mendedahkan versi sejarah?

Gunakan persistent segment tree: salin nod di sepanjang laluan kemas kini dan kongsi subpokok yang tidak disentuh. Setiap kemas kini menyalin kira-kira O(log n) nod, dan penuding punca (root pointer) mengenal pasti versi, jadi ruang bertambah mengikut bilangan kemas kini.