Segment tree biasa hanya mendukung point update: mengubah satu elemen array dalam O(log n). Namun banyak persoalan nyata memerlukan range update: “tambahkan v ke setiap elemen di indeks [l, r]”. Tanpa optimasi, range update butuh O(n) — kita harus mengunjungi setiap leaf di rentang tersebut. Untuk q operasi campuran update dan query, ini menjadi O(n·q). Lazy propagation mengatasi ini dengan menunda aplikasi update ke anak-anak node sampai anak tersebut benar-benar diakses. Hasilnya: range update menjadi O(log n) dan range query tetap O(log n). Pada Chapter ini kita membedah mekanisme lazy tag, implementasi range-add + range-sum lengkap, serta prinsip umum untuk operasi lain (range-assign, range-max).

Aturan: Masalah Range Update + Range Query #

Diberikan array A dengan n elemen. Dukung tiga operasi:

  1. Build: konstruksi dari array awal.
  2. range_add(l, r, v): tambahkan v ke A[i] untuk setiap i ∈ [l, r].
  3. range_sum(l, r): kembalikan Σ A[i] untuk i ∈ [l, r].

Implementasi naif: range_add loop i = l .. r → O(n). Lazy propagation: keduanya O(log n).

Mekanisme: Lazy Tag dan Push-Down #

Setiap node segment tree menyimpan dua nilai:

  • tree_[node]: aggregate (sum) dari segmen yang diwakili node.
  • lazy_[node]: update yang belum diterapkan ke anak-anak node, tetapi sudah diterapkan ke tree_[node] itu sendiri.

Invarian penting: tree_[node] selalu merefleksikan semua update yang sudah apply ke segmen node tersebut. lazy_[node] adalah update yang masih perlu di-propagate ke anak.

Operasi apply(node, lo, hi, val): terapkan update val ke seluruh segmen [lo, hi] yang diwakili node:

text 
tree_[node] += (hi - lo + 1) * val   // update aggregate (sum ditambah val untuk setiap elemen)
lazy_[node] += val                    // tandai bahwa anak-anak belum tahu tentang update ini

Operasi push_down(node, lo, hi): bila lazy_[node] != 0, terapkan ke kedua anak via apply, lalu reset lazy_[node] = 0. Dipanggil sebelum kita perlu mengakses anak-anak node.

Algoritma update(node, lo, hi, ql, qr, val):

  1. No overlap (qr < lo || hi < ql): return.
  2. Total overlap (ql ≤ lo && hi ≤ qr): apply(node, lo, hi, val), return. Lazy tag di-set, anak tidak disentuh.
  3. Partial overlap: push_down(node, lo, hi), lalu rekursi ke kedua anak, lalu tree_[node] = tree_[left] + tree_[right].

Algoritma query mirip — pada partial overlap, push_down dulu sebelum rekursi.

Implementasi Range-Add + Range-Sum #

cpp 
#include <iostream>
#include <vector>

class LazySegTree {
public:
    explicit LazySegTree(const std::vector<long long>& arr) {
        n_ = arr.size();
        tree_.assign(4 * n_, 0);
        lazy_.assign(4 * n_, 0);
        build(arr, 1, 0, n_ - 1);
    }

    // Tambah val ke setiap elemen di [l, r]
    void range_add(int l, int r, long long val) {
        update(1, 0, n_ - 1, l, r, val);
    }

    // Sum elemen di [l, r]
    long long range_sum(int l, int r) {
        return query(1, 0, n_ - 1, l, r);
    }

private:
    int n_;
    std::vector<long long> tree_, lazy_;

    void build(const std::vector<long long>& arr, int node, int lo, int hi) {
        if (lo == hi) { tree_[node] = arr[lo]; return; }
        int mid = (lo + hi) / 2;
        build(arr, 2*node, lo, mid);
        build(arr, 2*node+1, mid+1, hi);
        tree_[node] = tree_[2*node] + tree_[2*node+1];
    }

    void apply(int node, int lo, int hi, long long val) {
        tree_[node] += (long long)(hi - lo + 1) * val;
        lazy_[node] += val;
    }

    void push_down(int node, int lo, int hi) {
        if (lazy_[node] == 0) return;
        int mid = (lo + hi) / 2;
        apply(2*node, lo, mid, lazy_[node]);
        apply(2*node+1, mid+1, hi, lazy_[node]);
        lazy_[node] = 0;
    }

    void update(int node, int lo, int hi, int ql, int qr, long long val) {
        if (qr < lo || hi < ql) return;
        if (ql <= lo && hi <= qr) { apply(node, lo, hi, val); return; }
        push_down(node, lo, hi);
        int mid = (lo + hi) / 2;
        update(2*node, lo, mid, ql, qr, val);
        update(2*node+1, mid+1, hi, ql, qr, val);
        tree_[node] = tree_[2*node] + tree_[2*node+1];
    }

    long long query(int node, int lo, int hi, int ql, int qr) {
        if (qr < lo || hi < ql) return 0;
        if (ql <= lo && hi <= qr) return tree_[node];
        push_down(node, lo, hi);
        int mid = (lo + hi) / 2;
        return query(2*node, lo, mid, ql, qr)
             + query(2*node+1, mid+1, hi, ql, qr);
    }
};

int main() {
    std::vector<long long> arr = {1, 2, 3, 4, 5, 6, 7, 8};
    LazySegTree st(arr);

    std::cout << "sum [2,5] awal = " << st.range_sum(2, 5) << '\n';
    st.range_add(2, 5, 10);
    std::cout << "setelah add 10 ke [2,5], sum [2,5] = " << st.range_sum(2, 5) << '\n';
    std::cout << "sum [0,7] = " << st.range_sum(0, 7) << '\n';
    st.range_add(0, 3, 100);
    std::cout << "setelah add 100 ke [0,3], sum [0,7] = " << st.range_sum(0, 7) << '\n';
    std::cout << "sum [4,5] = " << st.range_sum(4, 5) << '\n';
    return 0;
}

Output yang Dihasilkan:

text 
sum [2,5] awal = 18
setelah add 10 ke [2,5], sum [2,5] = 58
sum [0,7] = 76
setelah add 100 ke [0,3], sum [0,7] = 476
sum [4,5] = 31

Bedah Kode Baris-per-Baris #

  1. tree_.assign(4 * n_, 0) dan lazy_.assign(4 * n_, 0): dua array paralel. tree_ menyimpan sum segmen, lazy_ menyimpan tag tertunda. Awal semua 0 (lazy=0 berarti “tidak ada update tertunda”).
  2. build: identik dengan segment tree biasa — post-order, leaf assign arr[lo], internal tree_[node] = tree_[left] + tree_[right]. Build tidak menyentuh lazy_ karena array awal tidak punya update tertunda.
  3. apply(node, lo, hi, val): inti dari lazy. Update tree_[node] langsung (sum += (hi-lo+1) * val karena val ditambah ke setiap elemen), dan tambah val ke lazy_[node]. Lazy tag bersifat akumulatif untuk operasi add (bukan overwrite).
  4. push_down(node, lo, hi): bila lazy_[node] != 0, terapkan lazy tag ke kedua anak via apply (dengan rentang masing-masing [lo, mid] dan [mid+1, hi]). Setelah itu reset lazy_[node] = 0.
  5. update tiga kasus:
    • No overlap: return tanpa lakukan apapun.
    • Total overlap: apply(node, lo, hi, val). Lazy tag di-set. Anak-anak tidak diakses — inilah yang membuat O(log n), bukan O(n).
    • Partial overlap: push_down dulu (anak perlu tahu tentang update tertunda sebelum kita rekursi ke mereka), lalu rekursi, lalu recompute tree_[node].
  6. query tiga kasus mirip, dengan push_down sebelum partial overlap. Tanpa push_down, anak masih menyimpan nilai lama dan query menjadi salah.
  7. Verifikasi hasil:
    • Awal: arr = [1,2,3,4,5,6,7,8], sum[2,5] = 3+4+5+6 = 18. ✓
    • Setelah add(2,5,10): arr = [1,2,13,14,15,16,7,8], sum[2,5] = 13+14+15+16 = 58. ✓
    • sum[0,7] = 1+2+13+14+15+16+7+8 = 76. ✓
    • Setelah add(0,3,100): arr = [101,102,113,114,15,16,7,8], sum[0,7] = 476. ✓
    • sum[4,5] = 15+16 = 31 (tidak terkena add 100 karena [4,5] tidak overlap dengan [0,3]). ✓

Generalisasi ke Operasi Lain #

Lazy propagation tidak terbatas pada range-add + range-sum. Pola umumnya:

  • Range-assign + range-sum: lazy tag = (value, is_assign). Apply overwrite seluruh segmen dengan satu nilai. apply(node, lo, hi, val): tree_[node] = (hi-lo+1) * val; lazy_[node] = {val, true}.
  • Range-add + range-min: apply: tree_[node] += val (min semua elemen naik sebesar val). Lazy tag = val (akumulatif).
  • Range-add + range-max: mirip dengan min.
  • Range-assign + range-min: lebih kompleks — lazy tag harus bisa “menimpa” tag sebelumnya.

Untuk lazy tag yang berinteraksi kompleks (mis. range-add + range-assign bersama), gunakan tag komposit dengan aturan merge yang jelas.

Kompleksitas #

OperasiKompleksitas
BuildO(n)
Range updateO(log n)
Range queryO(log n)
Memori8n (tree + lazy)

Ringkasan #

  • Lazy propagation memungkinkan range update O(log n) pada segment tree.
  • Setiap node menyimpan tree_ (aggregate selalu benar) dan lazy_ (update tertunda untuk anak).
  • apply: update tree langsung, set lazy tag (anak belum tahu).
  • push_down: terapkan lazy tag ke kedua anak, reset tag di node saat ini. Wajib sebelum akses anak.
  • Generalisasi: range-assign, range-min, range-max — pola serupa, hanya apply yang berbeda.
  • Kompleksitas: O(log n) per operasi, memori 8n.
  • Lanjutan: lazy tag komposit untuk multiple operasi (mis. range-add + range-assign bersama).