Segment Tree

Pada Chapter sebelumnya di Section tree, kita sudah membangun segment tree rekursif dasar untuk operasi sum dan min. Sekarang kita naik level: membangun segment tree generik berbasis template yang mendukung operasi apa pun (sum, min, max, gcd, custom merge), dan iterative segment tree (bottom-up) yang lebih cepat 2-3× untuk n besar. Memahami kedua varian ini penting karena segment tree adalah pondasi untuk topik lanjutan: lazy propagation (range update), persistent segment tree (versi historis), dan merge sort tree (range query kompleks). Pada Chapter ini kita juga mendiskusikan trade-off antara rekursif (mudah dibaca, fleksibel untuk extension) versus iteratif (cepat, ringkas).

Aturan: Operator Monoid dan Identitas #

Segment tree bekerja untuk operasi yang membentuk monoid — himpunan T dengan operasi biner ⊕ yang memenuhi:

1. Asosiatif: (a ⊕ b) ⊕ c = a ⊕ (b ⊕ c).
2. Identitas: ada e ∈ T sehingga a ⊕ e = a untuk semua a.

Contoh monoid:

• (int, +, 0) — penjumlahan.
• (int, min, +∞) — minimum.
• (int, max, -∞) — maksimum.
• (int, gcd, 0) — gcd (gcd(x, 0) = x).
• (int, &, 0xFFFFFFFF) — bitwise AND.

Bila operasi tidak komutatif (mis. (matrix, *, I)), segment tree tetap berlaku tetapi urutan operand harus dijaga saat merge.

Mekanisme: Template Generic Segment Tree #

Kita abstraksikan operasi ⊕ sebagai parameter Merge (callable). Identitas e sebagai parameter konstruksi. Hasilnya: satu kelas template yang berlaku untuk semua monoid.

Implementasi Generic dan Iterative #

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>

template<typename T, typename Merge>
class GenericSegmentTree {
public:
    GenericSegmentTree(const std::vector<T>& arr, T identity, Merge merge)
        : n_(arr.size()), identity_(identity), merge_(merge) {
        tree_.assign(4 * n_, identity_);
        build(arr, 1, 0, n_ - 1);
    }
    T query(int l, int r) const {
        return query_rec(1, 0, n_ - 1, l, r);
    }
    void update(int idx, T val) {
        update_rec(1, 0, n_ - 1, idx, val);
    }
private:
    int n_;
    T identity_;
    Merge merge_;
    std::vector<T> tree_;
    void build(const std::vector<T>& 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] = merge_(tree_[2*node], tree_[2*node+1]);
    }
    T query_rec(int node, int lo, int hi, int ql, int qr) const {
        if (qr < lo || hi < ql) return identity_;
        if (ql <= lo && hi <= qr) return tree_[node];
        int mid = (lo + hi) / 2;
        return merge_(query_rec(2*node, lo, mid, ql, qr),
                     query_rec(2*node+1, mid+1, hi, ql, qr));
    }
    void update_rec(int node, int lo, int hi, int idx, T val) {
        if (lo == hi) { tree_[node] = val; return; }
        int mid = (lo + hi) / 2;
        if (idx <= mid) update_rec(2*node, lo, mid, idx, val);
        else update_rec(2*node+1, mid+1, hi, idx, val);
        tree_[node] = merge_(tree_[2*node], tree_[2*node+1]);
    }
};

class IterSumTree {
public:
    explicit IterSumTree(const std::vector<long long>& arr) {
        n_ = arr.size();
        tree_.assign(2 * n_, 0);
        for (size_t i = 0; i < n_; ++i) tree_[n_ + i] = arr[i];
        for (int i = n_ - 1; i >= 1; --i) tree_[i] = tree_[2*i] + tree_[2*i+1];
    }
    void update(int idx, long long val) {
        idx += n_;
        tree_[idx] = val;
        for (idx /= 2; idx >= 1; idx /= 2) tree_[idx] = tree_[2*idx] + tree_[2*idx+1];
    }
    long long query(int l, int r) const {
        l += n_; r += n_;
        long long s = 0;
        while (l <= r) {
            if (l % 2 == 1) s += tree_[l++];
            if (r % 2 == 0) s += tree_[r--];
            l /= 2; r /= 2;
        }
        return s;
    }
private:
    size_t n_;
    std::vector<long long> tree_;
};

int main() {
    std::vector<int> arr = {3, 1, 4, 1, 5, 9, 2, 6};

    auto sum_tree = GenericSegmentTree<int, std::function<int(int,int)>>(
        arr, 0, [](int a, int b){ return a + b; });
    auto max_tree = GenericSegmentTree<int, std::function<int(int,int)>>(
        arr, -1000000000, [](int a, int b){ return std::max(a, b); });
    auto gcd_tree = GenericSegmentTree<int, std::function<int(int,int)>>(
        arr, 0, [](int a, int b){ return std::gcd(a, b); });

    std::cout << "sum [2,5]  = " << sum_tree.query(2, 5) << '\n';
    std::cout << "max [2,5]  = " << max_tree.query(2, 5) << '\n';
    std::cout << "gcd [2,5]  = " << gcd_tree.query(2, 5) << '\n';

    sum_tree.update(3, 100);
    std::cout << "setelah update idx 3 = 100, sum [2,5] = " << sum_tree.query(2, 5) << '\n';

    std::vector<long long> arr2 = {5, 2, 8, 1, 9};
    IterSumTree iter(arr2);
    std::cout << "\nIter sum [0,4] = " << iter.query(0, 4) << '\n';
    std::cout << "Iter sum [1,3] = " << iter.query(1, 3) << '\n';
    iter.update(2, 20);
    std::cout << "setelah update idx 2 = 20: sum [0,4] = " << iter.query(0, 4) << '\n';
    return 0;
}

Output yang Dihasilkan:

sum [2,5]  = 19
max [2,5]  = 9
gcd [2,5]  = 1
setelah update idx 3 = 100, sum [2,5] = 118

Iter sum [0,4] = 25
Iter sum [1,3] = 11
setelah update idx 2 = 20: sum [0,4] = 37

Bedah Kode Baris-per-Baris #

1. template<typename T, typename Merge>: dua parameter template — T tipe data elemen, Merge tipe callable (lambda, function pointer, functor) yang menerima dua T dan mengembalikan satu T.
2. identity_(identity): nilai identitas e disimpan sebagai member, dipakai saat query_rec menemui no-overlap (return e).
3. tree_.assign(4 * n_, identity_): ukuran aman 4n untuk segment tree rekursif. Awali semua node dengan identitas sebagai defensif.
4. build: rekursi post-order — bangun anak kiri dan kanan dulu, lalu gabung dengan merge_. Saat lo == hi, assign elemen array (leaf).
5. query_rec: tiga kasus overlap. Pada no-overlap, return identity_ (untuk sum = 0, untuk min = +∞, untuk gcd = 0). Pada total overlap, return tree_[node]. Pada partial, rekursi dan gabung.
6. update_rec: turun ke leaf, assign val baru, lalu pada saat unwind recompute parent via merge_.
7. std::function<int(int,int)> sebagai Merge: paling fleksibel (lambda dengan capture), tetapi ada overhead call vs functor. Untuk performa maksimal, gunakan struct functor dan lewatkan tipe ke template.
8. IterSumTree: konvensi iterative — leaf di [n, 2n-1], build dari bawah ke atas i = n-1 .. 1. tree_[i] = tree_[2i] + tree_[2i+1].
9. query iterative: dua pointer l dan r dimulai di leaf. Saat l ganjil (l % 2 == 1), node l adalah anak kanan parent → tidak tercakup penuh → ambil dan l++. Saat r genap (r % 2 == 0), node r adalah anak kiri parent → ambil dan r--. Lalu naik l /= 2; r /= 2.
10. Hasil verifikasi: sum [2,5] = 4+1+5+9 = 19, max = 9, gcd = gcd(4,1,5,9) = 1. Setelah update idx 3 = 100: sum [2,5] = 4+100+5+9 = 118. Iterative tree menghasilkan output identik dengan rekursif — keduanya benar.

Kompleksitas #

Trade-off dan Kapan Memilih #

• Rekursif generic: pilihan saat kita butuh fleksibilitas operasi, mudah di-extend ke lazy propagation atau persistent.
• Iterative: pilihan untuk sum/min/max sederhana dengan n besar (>10^6). Lebih cepat dan hemat memori.
• Fenwick tree: bila hanya butuh prefix sum dan point update, Fenwick lebih ringan (memori n, konstanta paling kecil).

Ringkasan #

• Segment tree adalah binary tree yang menyimpan monoid (T, ⊕, e) untuk setiap segmen array.
• Generic template memungkinkan satu implementasi untuk semua monoid: sum, min, max, gcd, bitwise.
• Identitas e penting: +0 untuk sum, +∞ untuk min, -∞ untuk max, 0 untuk gcd.
• Iterative (bottom-up) ~2-3× lebih cepat dan hemat memori (2n vs 4n).
• Kompleksitas: build O(n), query O(log n), point update O(log n).
• Pilihan struktur: Fenwick untuk prefix-sum only, segment tree untuk operasi umum, sparse table untuk query-only idempotent.
• Lanjutan: lazy propagation (range update), persistent (versi historis), merge-sort tree (range query kompleks), lihat Chapter selanjutnya.