Bayangkan kita punya array A berisi n elemen dan harus menjawab banyak query berulang: “berapa jumlah elemen pada range [l, r]?", “berapa nilai minimum pada [l, r]?". Solusi naif: iterasi A[l..r] setiap query, O(n) per query. Untuk q query, total O(n·q). Bila n = q = 100rb, total 10 miliar operasi — terlalu lambat. Segment tree menyelesaikan masalah ini dengan praproses O(n) dan menjawab setiap range query dalam O(log n). Bonus: update satu elemen juga O(log n), jauh lebih cepat dari prefix sum array yang O(n) per update. Pada Chapter ini kita akan mengimplementasikan segment tree rekursif dan iteratif, mendukung operasi sum, min, dan max, serta memahami kapan segment tree unggul dibanding alternatif.

Inti Segment Tree #

Segment tree menyimpan gabungan (aggregate) dari setiap segmen array dalam node tree. Root menyimpan aggregate seluruh array [0, n-1]. Anak kiri menyimpan aggregate [0, (n-1)/2], anak kanan menyimpan [(n-1)/2 + 1, n-1], dan seterusnya sampai leaf yang masing-masing menyimpan satu elemen.

Pada tree di atas, array A = [1, 2, 3, 3, 4, 8]. Root menyimpan sum total 21. Untuk query sum [2, 5] = 3+3+4+8 = 18, segment tree menggabungkan node [2,2] (sum=3) dan [3,5] (sum=15) → 18.

Build, Query, dan Update #

Build (O(n)) #

Bangun segment tree dari array secara rekursif post-order:

cpp 
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

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

    int sum(int l, int r) const { return query_sum(1, 0, n_ - 1, l, r); }

    void update(int idx, int val) { update_rec(1, 0, n_ - 1, idx, val); }

private:
    int n_;
    std::vector<int> tree_;

    void build(const std::vector<int>& 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];
    }

    int query_sum(int node, int lo, int hi, int ql, int qr) const {
        if (qr < lo || hi < ql) return 0;             // no overlap
        if (ql <= lo && hi <= qr) return tree_[node]; // total overlap
        int mid = (lo + hi) / 2;
        return query_sum(2*node,     lo,    mid, ql, qr)
             + query_sum(2*node + 1, mid+1, hi,  ql, qr);
    }

    void update_rec(int node, int lo, int hi, int idx, int 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] = tree_[2*node] + tree_[2*node + 1];
    }
};

int main() {
    std::vector<int> arr = {1, 2, 3, 3, 4, 8};
    SegmentTree st(arr);

    std::cout << "sum [0,5] = " << st.sum(0, 5) << '\n';
    std::cout << "sum [2,5] = " << st.sum(2, 5) << '\n';
    std::cout << "sum [1,3] = " << st.sum(1, 3) << '\n';

    st.update(3, 10);  // arr[3] = 10 (sebelumnya 3)
    std::cout << "\nSetelah update arr[3] = 10:\n";
    std::cout << "sum [0,5] = " << st.sum(0, 5) << '\n';
    std::cout << "sum [2,5] = " << st.sum(2, 5) << '\n';

    return 0;
}

Output yang Dihasilkan:

text 
sum [0,5] = 21
sum [2,5] = 18
sum [1,3] = 8

Setelah update arr[3] = 10:
sum [0,5] = 28
sum [2,5] = 25
  1. tree_.assign(4 * n_, 0): segment tree memerlukan array berukuran 4n (aman) atau 2 × next_pow2(n) (optimal). Ukuran 4n melindungi dari edge case n ganjil.
  2. build: post-order rekursif. Bila lo == hi (leaf), assign elemen array. Bila bukan, rekursi ke anak kiri [lo, mid] dan anak kanan [mid+1, hi], lalu gabung dengan operator (sum = left + right).
  3. query_sum: tiga kasus overlap:
    • No overlap (qr < lo || hi < ql): return 0 (identitas untuk sum).
    • Total overlap (ql <= lo && hi <= qr): return tree_[node].
    • Partial overlap: rekursi ke kedua anak dan gabung hasilnya.
  4. update_rec: turun ke leaf yang sesuai dengan idx. Setelah update leaf, naik sambil update parent: tree_[parent] = tree_[left] + tree_[right].
  5. Hasil sum [2,5]: 3 + 3 + 4 + 8 = 18. Sesuai ekspektasi. Setelah update arr[3] = 10, sum [2,5] = 3 + 10 + 4 + 8 = 25.

Iterative Segment Tree (Lebih Cepat) #

Versi iteratif menghindari overhead rekursi, ~2-3× lebih cepat untuk n besar. Memakai konvensi array 1-indexed dengan leaf di posisi [n, 2n-1].

cpp 
#include <iostream>
#include <vector>

class IterSegmentTree {
public:
    explicit IterSegmentTree(const std::vector<int>& arr) {
        n_ = arr.size();
        tree_.assign(2 * n_, 0);
        for (int 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, int val) {
        idx += n_;
        tree_[idx] = val;
        for (idx /= 2; idx >= 1; idx /= 2) {
            tree_[idx] = tree_[2*idx] + tree_[2*idx + 1];
        }
    }

    int sum(int l, int r) const {
        l += n_; r += n_;
        int 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:
    int n_;
    std::vector<int> tree_;
};

int main() {
    std::vector<int> arr = {1, 2, 3, 3, 4, 8};
    IterSegmentTree st(arr);

    std::cout << "Iter sum [0,5] = " << st.sum(0, 5) << '\n';
    std::cout << "Iter sum [2,5] = " << st.sum(2, 5) << '\n';

    st.update(3, 10);
    std::cout << "Setelah update arr[3]=10: sum [0,5] = " << st.sum(0, 5) << '\n';
    return 0;
}

Output yang Dihasilkan:

text 
Iter sum [0,5] = 21
Iter sum [2,5] = 18
Setelah update arr[3]=10: sum [0,5] = 28
  1. Leaf di [n, 2n-1]: konvensi iterative tree meletakkan elemen array pada indeks n sampai 2n-1. Indeks n adalah leaf ke-0, n+1 leaf ke-1, dst.
  2. Build dari bawah ke atas: loop i = n-1 hingga 1, setiap node adalah gabungan dua anak 2i dan 2i+1.
  3. update iteratif: setelah update leaf, naik dengan idx /= 2 sambil menggabung ulang parent.
  4. sum iteratif: dua pointer l dan r dari leaf ke root. Bila l ganjil → node tersebut adalah anak kanan parent → tambahkan ke hasil lalu l++. Bila r genap → anak kiri parent → tambahkan ke hasil lalu r--. Kedua pointer naik dengan /= 2.
  5. Hasil sesuai versi rekursif — keduanya menghasilkan output identik. Iterative hanya lebih cepat.

Variasi: Min/Max Query #

Mengganti operator dari + ke min atau max. Identitas juga berubah: identitas min = +∞, identitas max = -∞.

cpp 
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

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

    int range_min(int l, int r) const {
        return query_min(1, 0, n_ - 1, l, r);
    }

    void update(int idx, int val) { update_rec(1, 0, n_ - 1, idx, val); }

private:
    int n_;
    std::vector<int> tree_;

    void build(const std::vector<int>& 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] = std::min(tree_[2*node], tree_[2*node + 1]);
    }

    int query_min(int node, int lo, int hi, int ql, int qr) const {
        if (qr < lo || hi < ql) return INT_MAX;       // identity for min
        if (ql <= lo && hi <= qr) return tree_[node];
        int mid = (lo + hi) / 2;
        return std::min(query_min(2*node,     lo,    mid, ql, qr),
                        query_min(2*node + 1, mid+1, hi,  ql, qr));
    }

    void update_rec(int node, int lo, int hi, int idx, int 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] = std::min(tree_[2*node], tree_[2*node + 1]);
    }
};

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

    std::cout << "min [0,5] = " << st.range_min(0, 5) << '\n';
    std::cout << "min [0,2] = " << st.range_min(0, 2) << '\n';
    std::cout << "min [3,5] = " << st.range_min(3, 5) << '\n';
    std::cout << "min [2,4] = " << st.range_min(2, 4) << '\n';

    st.update(2, 0);  // arr[2] = 0
    std::cout << "Setelah update arr[2]=0: min [0,5] = " << st.range_min(0, 5) << '\n';
    return 0;
}

Output yang Dihasilkan:

text 
min [0,5] = 1
min [0,2] = 2
min [3,5] = 1
min [2,4] = 1
Setelah update arr[2]=0: min [0,5] = 0
  1. Identitas INT_MAX: bila ada no-overlap, return INT_MAX (identitas minimum). std::min(x, INT_MAX) = x.
  2. Build/query identik dengan sum version — hanya operator yang berubah: + → std::min.
  3. Hasil min [0,5] = 1: nilai terkecil dalam array [5, 2, 8, 1, 9, 3] adalah 1 (di indeks 3).
  4. Setelah update arr[2] = 0: minimum baru = 0.

Kompleksitas dan Perbandingan #

StrukturBuildRange queryPoint updateMemori
Naif arrayO(1)O(n)O(1)O(n)
Prefix sumO(n)O(1)O(n)O(n)
Segment treeO(n)O(log n)O(log n)O(4n)
Fenwick tree (BIT)O(n)O(log n)O(log n)O(n)

Ringkasan #

  • Segment tree: binary tree yang menyimpan aggregate (sum/min/max) dari setiap segmen array dalam node.
  • Tiga operasi utama: build O(n), range query O(log n), point update O(log n).
  • Implementasi rekursif mudah dibaca; iteratif ~2-3× lebih cepat untuk n besar.
  • Operator dapat diganti: sum (+0), min (+∞), max (−∞), GCD (identity = 0), dll.
  • Segment tree unggul saat update + query seimbang. Prefix sum unggul saat query-only.
  • Trade-off memori: 4n (rekursif) atau 2n (iteratif) — lebih besar dari prefix sum n.
  • Variasi lanjutan: lazy propagation untuk range update (update [l,r] sekaligus), persistent segment tree untuk akses versi historis. Dibahas di Section 22 (Struktur Data Lanjutan).