Wawancara Koding: Bagaimana cara membangun lazy segment tree untuk range add dan range sum?

Pertanyaan dan cakupan

Diberikan sebuah array integer dengan panjang n, proses dua operasi online: tambahkan delta ke setiap nilai dalam interval tertutup [l, r], dan kembalikan jumlah dari [l, r]. Targetkan konstruksi O(n), O(log n) per operasi, dan ruang ekstra O(n). Nyatakan bahwa interval bersifat tertutup, delta dapat bernilai negatif, dan persistensi berada di luar cakupan kecuali diminta.

Apa yang diuji oleh pewawancara

Tuliskan invariannya terlebih dahulu: tree[p] selalu merupakan jumlah sebenarnya untuk interval node tersebut, sedangkan lazy[p] adalah kenaikan seragam yang sudah disertakan dalam jumlah tersebut tetapi belum diterapkan ke anak-anaknya. Jawaban yang kuat hanya memperbarui node yang tercakup sepenuhnya, melakukan push sebelum traversal parsial, dan mengalikan kenaikan dengan panjang interval yang tercakup.

Klarifikasi sebelum koding

1. Apakah pembaruan berupa penambahan, penugasan (assignment), atau nilai minimum rentang? Aturan komposisi lazy-tag mereka berbeda.
2. Apakah agregatnya berupa penjumlahan, nilai minimum, atau nilai maksimum? Penggabungan node dan rumus tag akan berubah.
3. Apakah intervalnya tertutup? Jawaban ini menggunakan interval tertutup [l, r]; interval setengah terbuka memerlukan pembagian dan panjang yang konsisten.
4. Seberapa besar nilai yang dapat muncul? tree[p] + delta * length dapat meluap (overflow) pada integer 32-bit, jadi pilihlah tipe data yang lebih besar.

Solusi yang direkomendasikan dan penurunannya

Simpan binary tree implisit dalam array. Sebuah node [lo, hi] terbagi pada mid menjadi [lo, mid] dan [mid+1, hi]. Untuk pembaruan yang tercakup sepenuhnya, tambahkan delta * (hi-lo+1) ke tree[p] dan akumulasikan delta dalam lazy[p]; nilai anak dapat dibiarkan tidak tersentuh hingga dibutuhkan.

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

Selesaikan add dan sum secara rekursif dengan invarian yang sama: panggil _apply pada cakupan penuh; panggil _push sebelum cakupan parsial; hitung ulang node induk dari anak-anaknya setelah kembali. Setiap level hanya mengunjungi sejumlah node batas yang konstan, sehingga pembaruan dan kueri bernilai O(log n) dan penyimpanan adalah O(n).

Alternatif dan pertimbangan (trade-offs)

Untuk pembaruan titik (point update) ditambah prefix sum, Fenwick tree lebih pendek dan memiliki konstanta yang lebih kecil. Untuk penambahan rentang offline yang diikuti oleh satu pembacaan akhir, difference array lebih sederhana. Lazy segment tree sebanding dengan kompleksitasnya saat pembaruan rentang online dan agregat rentang ada secara bersamaan. Penugasan rentang (range assignment) memerlukan tag "has assignment" tambahan dan aturan prioritas yang eksplisit: penugasan menggantikan penugasan lama dan tag penambahan, sedangkan penambahan selanjutnya diakumulasikan setelahnya.

Mode kegagalan, batas, dan contoh kasus salah

• Melupakan panjang interval membuat penambahan 3 ke [2, 5] meningkatkan jumlah sebesar 3, bukan 12.
• Melakukan rekursi setelah cakupan penuh menghilangkan lazy propagation dan dapat menerapkan pembaruan berulang kali.
• Gagal membersihkan tag setelah push akan menerapkan kenaikan yang sama lagi pada kunjungan berikutnya.
• Tidak menghitung ulang induk setelah pembaruan parsial membuat kueri cakupan penuh berikutnya menjadi usang (stale).
• Mencampur interval tertutup dan setengah terbuka menyebabkan kesalahan selisih satu elemen atau mid+1; validasi array kosong, l > r, dan n=0 pada batas.

Daftar periksa pengujian dan verifikasi

Gunakan array naif sebagai oracle, buat pembaruan dan kueri acak, lalu bandingkan setelah setiap operasi. Sertakan rentang satu elemen, rentang penuh, kedua batas, delta negatif, tumpang tindih berulang, dan nilai yang semuanya sama. Pastikan bahwa induk sama dengan jumlah anak-anaknya setelah panggilan rekursif, dan periksa bahwa tipe integer yang dipilih tidak meluap pada input yang besar. Tambahkan uji kesetaraan jika menerapkan tata letak iteratif.

Pertanyaan lanjutan

Bagaimana range assignment dan range add dapat berdampingan?

Simpan tag assignment opsional dan tag add per node. Assignment baru menggantikan assignment lama dan tag add; add baru diakumulasikan setelah assignment. Lakukan push assignment terlebih dahulu dan add kedua. Urutan tersebut adalah aturan kebenarannya.

Bagaimana cara mendukung range minimum?

Simpan interval minimum alih-alih jumlah; range add masih menambahkan delta ke nilai minimum tersebut, sehingga lazy tag tetap sederhana. Range chmin atau chmax memerlukan invarian yang lebih kaya seperti segment-tree beats.

Bagaimana cara mengekspos versi historis?

Gunakan persistent segment tree: salin node di sepanjang jalur pembaruan dan bagikan subtree yang tidak tersentuh. Setiap pembaruan menyalin sekitar O(log n) node, dan sebuah pointer root mengidentifikasi versi, sehingga ruang bertambah seiring dengan jumlah pembaruan.