Sparse Table

Sparse table adalah struktur data statis yang menjawab query rentang idempotent (seperti min, max, gcd) dalam O(1) setelah prekomputasi O(n log n). Bayangkan kita sering ditanya: “Berapa nilai minimum pada rentang [l, r]?” Tanpa sparse table, setiap pertanyaan butuh loop O(n). Dengan sparse table, satu operasi bitwise + dua lookup tabel. Pada Chapter ini kita akan membedah konstruksi sparse table, rumus query, dan mengapa ia hanya cocok untuk operasi idempotent. Pemahaman sparse table menjadi dasar untuk struktur lanjutan seperti segment tree dan LCA (Lowest Common Ancestor).

Konsep Inti: Overlapping Intervals #

Mekanisme: Potongan-Potongan Berpangkat Dua #

Sparse table menyimpan jawaban untuk setiap rentang yang panjangnya adalah pangkat dua. Tabel st[k][i] menyimpan jawaban query pada rentang [i, i + 2^k - 1]. Dengan k hingga ⌊log₂ n⌋, total sel tabel adalah n × log n.

Untuk menjawab query rentang [l, r]:

k = floor(log2(r - l + 1))
answer = combine(st[k][l], st[k][r - 2^k + 1])

Dua interval [l, l+2^k-1] dan [r-2^k+1, r] masing-masing berukuran 2^k, tumpang tindih di tengah, dan bersama-sama mencakup [l, r]. Bila operasi combine adalah idempotent (mis. min, max, gcd), overlap tidak masalah — min(x, x) = x.

Operasi Idempotent vs Non-Idempotent #

Untuk operasi non-idempotent seperti sum, overlap menyebabkan elemen dihitung dua kali. Gunakan prefix sum untuk sum (O(1) dengan precompute O(n)), atau segment tree untuk operasi non-idempotent dengan update dinamis.

Konstruksi Sparse Table #

Mekanisme: Pengisian Bertingkat #

Tabel st[k][i] diisi dengan urutan k menaik. Untuk k = 0: st[0][i] = a[i] (interval panjang 1). Untuk k > 0:

st[k][i] = combine(st[k-1][i], st[k-1][i + 2^(k-1)])

Interval panjang 2^k dibagi menjadi dua interval panjang 2^(k-1) yang bersebelahan. Keduanya dihitung pada iterasi sebelumnya, sehingga konstruksi berjalan bottom-up.

Kode: Build Sparse Table untuk Range Minimum Query #

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

class SparseTableMin {
    std::vector<std::vector<int>> st_;
    std::vector<int> log2_;
public:
    explicit SparseTableMin(const std::vector<int>& a) {
        int n = static_cast<int>(a.size());
        int K = static_cast<int>(std::floor(std::log2(n))) + 1;

        // Precompute log2 untuk query O(1)
        log2_.resize(n + 1);
        log2_[1] = 0;
        for (int i = 2; i <= n; ++i) log2_[i] = log2_[i / 2] + 1;

        st_.assign(K, std::vector<int>(n));
        st_[0] = a;

        for (int k = 1; k < K; ++k) {
            int len = 1 << (k - 1);
            for (int i = 0; i + (1 << k) - 1 < n; ++i) {
                st_[k][i] = std::min(st_[k-1][i], st_[k-1][i + len]);
            }
        }
    }

    int query(int l, int r) const {
        int k = log2_[r - l + 1];
        return std::min(st_[k][l], st_[k][r - (1 << k) + 1]);
    }
};

int main() {
    std::vector<int> a = {7, 2, 3, 0, 5, 10, 3, 12, 18};
    SparseTableMin st(a);

    std::cout << "min(0, 4)   = " << st.query(0, 4)   << '\n';
    std::cout << "min(2, 5)   = " << st.query(2, 5)   << '\n';
    std::cout << "min(0, 8)   = " << st.query(0, 8)   << '\n';
    std::cout << "min(5, 5)   = " << st.query(5, 5)   << '\n';
    std::cout << "min(4, 7)   = " << st.query(4, 7)   << '\n';
    return 0;
}

Output yang Dihasilkan:

min(0, 4)   = 0
min(2, 5)   = 0
min(0, 8)   = 0
min(5, 5)   = 10
min(4, 7)   = 3

1. Baris int K = std::floor(std::log2(n)) + 1;: jumlah baris tabel = ⌊log₂ n⌋ + 1. Untuk n = 9, K = 4 (rentang panjang 1, 2, 4, 8).
2. Baris log2_[i] = log2_[i / 2] + 1;: precompute log2 untuk semua nilai dari 1 hingga n. Memungkinkan query O(1) tanpa pemanggilan std::log2 (yang lebih lambat).
3. Baris st_[k][i] = std::min(st_[k-1][i], st_[k-1][i + len]);: build bottom-up. Interval panjang 2^k digabung dari dua interval panjang 2^(k-1) yang bersebelahan.
4. Baris int k = log2_[r - l + 1];: ambil k terbesar sehingga 2^k <= r - l + 1. Interval panjang 2^k muat di dalam [l, r].
5. Baris return std::min(st_[k][l], st_[k][r - (1 << k) + 1]);: dua interval st_[k][l] (mulai dari l) dan st_[k][r - 2^k + 1] (berakhir di r) — bersama mencakup [l, r]. Overlap di tengah tidak masalah karena min idempotent.
6. Verifikasi min(4, 7) = 3: rentang [4, 7] = {5, 10, 3, 12}, minimumnya 3. Sesuai.

Mengapa Sparse Table Tidak untuk Sum? #

Mekanisme: Overlap Menyebabkan Double Counting #

Untuk query sum(l, r), sparse table akan menambahkan dua interval:

sum(l, r) = st_sum[k][l] + st_sum[k][r - 2^k + 1]

Tapi dua interval tersebut tumpang tindih di tengah. Elemen-elemen di overlap akan ditambahkan dua kali — hasil salah. Inilah alasan sparse table hanya cocok untuk operasi idempotent.

Demonstrasi Numerik #

Untuk array a = {1, 2, 3, 4, 5} dan query sum(0, 4):

• k = log2(5) = 2, sehingga 2^k = 4.
• st_sum[2][0] = 1 + 2 + 3 + 4 = 10.
• st_sum[2][4 - 4 + 1] = st_sum[2][1] = 2 + 3 + 4 + 5 = 14.
• st_sum[2][0] + st_sum[2][1] = 24. Tapi jawaban benar adalah 1 + 2 + 3 + 4 + 5 = 15.

Selisih 24 - 15 = 9 = 2 + 3 + 4 (elemen overlap ditambah dua kali). Operasi sum tidak idempotent — sparse table gagal.

Sparse Table untuk Range GCD #

Kode: Sparse Table dengan Template #

Kita dapat memperumum sparse table menjadi template yang menerima fungsi combine apa pun (asalkan idempotent). Berikut implementasi untuk gcd:

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

class SparseTableGCD {
    std::vector<std::vector<int>> st_;
    std::vector<int> log2_;
public:
    explicit SparseTableGCD(const std::vector<int>& a) {
        int n = static_cast<int>(a.size());
        int K = 1;
        while ((1 << K) <= n) ++K;

        log2_.resize(n + 1);
        log2_[1] = 0;
        for (int i = 2; i <= n; ++i) log2_[i] = log2_[i / 2] + 1;

        st_.assign(K, std::vector<int>(n));
        st_[0] = a;
        for (int k = 1; k < K; ++k) {
            for (int i = 0; i + (1 << k) - 1 < n; ++i) {
                st_[k][i] = std::gcd(st_[k-1][i], st_[k-1][i + (1 << (k-1))]);
            }
        }
    }

    int query(int l, int r) const {
        int k = log2_[r - l + 1];
        return std::gcd(st_[k][l], st_[k][r - (1 << k) + 1]);
    }
};

int main() {
    std::vector<int> a = {12, 18, 24, 36, 9, 27, 81};
    SparseTableGCD st(a);

    std::cout << "gcd(0, 3) = " << st.query(0, 3) << '\n';
    std::cout << "gcd(2, 4) = " << st.query(2, 4) << '\n';
    std::cout << "gcd(4, 6) = " << st.query(4, 6) << '\n';
    std::cout << "gcd(0, 6) = " << st.query(0, 6) << '\n';
    return 0;
}

Output yang Dihasilkan:

gcd(0, 3) = 6
gcd(2, 4) = 3
gcd(4, 6) = 9
gcd(0, 6) = 3

1. Baris while ((1 << K) <= n) ++K;: hitung K tanpa std::log2 — alternatif yang lebih deterministik. K adalah jumlah pangkat dua yang muat dalam n.
2. Baris st_[k][i] = std::gcd(st_[k-1][i], st_[k-1][i + (1 << (k-1))]);: konstruksi bottom-up. std::gcd dari C++17 menggantikan implementasi manual Euclidean.
3. Baris return std::gcd(st_[k][l], st_[k][r - (1 << k) + 1]);: query dengan dua interval tumpang tindih. gcd idempotent — gcd(x, x) = x — sehingga overlap aman.
4. Verifikasi gcd(0, 3) = 6: rentang {12, 18, 24, 36}, FPB = 6. Sesuai (12 = 2²·3, 18 = 2·3², 24 = 2³·3, 36 = 2²·3²; FPB = 2·3 = 6).

Kompleksitas dan Perbandingan #

Sparse table unggul saat: array statik + banyak query + operasi idempotent. Bila ada update, segment tree lebih baik meski query sedikit lebih lambat.

Ringkasan #

• Sparse table adalah struktur statis untuk range query idempotent (min, max, gcd, bitwise AND/OR).
• Build O(n log n), query O(1). Memori O(n log n).
• Query memanfaatkan dua interval panjang 2^k yang tumpang tindih — idempotensi membuat overlap aman.
• Operasi non-idempotent (sum, product, xor) tidak cocok — gunakan prefix sum atau segment tree.
• Untuk array dinamis dengan update, segment tree atau Fenwick tree adalah pilihan lebih tepat.