Sparse Table

Sparse table menyimpan jawaban untuk setiap range yang panjangnya adalah pangkat dua. Dengan prekalkulasi log dan strategi overlap, query O(1) untuk operasi idempotent — yaitu operasi yang hasilnya tidak berubah bila suatu elemen dihitung dua kali: min(x, x) = x, max(x, x) = x, gcd(x, x) = x. Sedangkan operasi sum, xor, product non-idempotent — menghitung elemen dua kali menghasilkan jawaban salah. Untuk operasi non-idempotent, sparse table standar tidak bisa dipakai karena strategi overlap-then-merge menggandakan elemen. Solusinya: disjoint sparse table yang menjaga partisi bebas overlap. Pada Chapter ini kita membedah keduanya: sparse table idempotent klasik dan disjoint sparse table untuk operasi non-idempotent.

Aturan: Idempotent vs Non-idempotent #

Operasi ⊕ idempotent bila ⊕(x, x) = x untuk semua x.

Sparse table standar memakai trik: untuk query [l, r] dengan len = r - l + 1, ambil k = floor(log2(len)). Jawaban = merge(table[k][l], table[k][r - 2^k + 1]). Kedua segmen [l, l+2^k-1] dan [r-2^k+1, r] overlap tetapi karena operasi idempotent, overlap tidak menghasilkan kesalahan.

Mekanisme: Build Level-by-Level #

Sparse table level k menyimpan jawaban untuk range [i, i + 2^k - 1] di table[k][i]. Build dari level 0 (range length 1) naik ke level K = floor(log2(n)).

• table[0][i] = arr[i].
• table[k][i] = merge(table[k-1][i], table[k-1][i + 2^(k-1)]) — gabung dua segmen berurutan masing-masing panjang 2^(k-1).

Query [l, r]:

• k = log[r - l + 1].
• result = merge(table[k][l], table[k][r - 2^k + 1]).

Kedua segmen memiliki panjang 2^k ≥ setengah dari len, jadi union mereka mencakup [l, r] sepenuhnya (overlap di tengah).

Implementasi Sparse Table (Min) dan Disjoint Sparse Table (Sum) #

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

class SparseTable {
public:
    explicit SparseTable(const std::vector<int>& arr) {
        n_ = arr.size();
        int K = std::max(1, (int)std::log2((double)n_) + 1);
        table_.assign(K, std::vector<int>(n_));
        for (int i = 0; i < n_; ++i) table_[0][i] = arr[i];
        for (int k = 1; (1 << k) <= n_; ++k) {
            for (int i = 0; i + (1 << k) - 1 < n_; ++i) {
                table_[k][i] = std::min(table_[k-1][i],
                                        table_[k-1][i + (1 << (k-1))]);
            }
        }
        log_.assign(n_ + 1, 0);
        for (int i = 2; i <= n_; ++i) log_[i] = log_[i / 2] + 1;
    }
    int query(int l, int r) const {
        int k = log_[r - l + 1];
        return std::min(table_[k][l], table_[k][r - (1 << k) + 1]);
    }
private:
    int n_;
    std::vector<std::vector<int>> table_;
    std::vector<int> log_;
};

class DisjointSparseTable {
public:
    explicit DisjointSparseTable(const std::vector<long long>& arr) {
        n_ = arr.size();
        int K = 1;
        while ((1 << K) < 2 * n_) ++K;
        K = std::max(K, 2);
        table_.assign(K, std::vector<long long>(n_, 0));
        for (int i = 0; i < n_; ++i) table_[0][i] = arr[i];
        for (int k = 1; k < K; ++k) {
            int step = 1 << (k - 1);
            for (int mid = step; mid < n_; mid += step * 2) {
                int L = std::max(0, mid - step);
                int R = std::min(n_ - 1, mid + step - 1);
                // Left half [L, mid-1]: table_[k][i] = sum(arr[i..mid-1])
                table_[k][mid - 1] = arr[mid - 1];
                for (int i = mid - 2; i >= L; --i)
                    table_[k][i] = arr[i] + table_[k][i + 1];
                // Right half [mid, R]: table_[k][i] = sum(arr[mid..i])
                table_[k][mid] = arr[mid];
                for (int i = mid + 1; i <= R; ++i)
                    table_[k][i] = table_[k][i - 1] + arr[i];
            }
        }
    }
    long long query(int l, int r) const {
        if (l == r) return table_[0][l];
        int k = 32 - __builtin_clz((unsigned)(l ^ r));
        return table_[k][l] + table_[k][r];
    }
private:
    int n_;
    std::vector<std::vector<long long>> table_;
};

int main() {
    std::vector<int> arr = {7, 2, 3, 1, 5, 9, 4, 6};
    SparseTable st(arr);
    std::cout << "SparseTable (min):\n";
    std::cout << "  min[1,5] = " << st.query(1, 5) << '\n';
    std::cout << "  min[0,7] = " << st.query(0, 7) << '\n';
    std::cout << "  min[3,3] = " << st.query(3, 3) << '\n';

    std::vector<long long> arr2 = {1, 2, 3, 4, 5, 6, 7, 8};
    DisjointSparseTable dst(arr2);
    std::cout << "\nDisjointSparseTable (sum):\n";
    std::cout << "  sum[1,5] = " << dst.query(1, 5) << '\n';
    std::cout << "  sum[0,7] = " << dst.query(0, 7) << '\n';
    std::cout << "  sum[2,4] = " << dst.query(2, 4) << '\n';
    std::cout << "  sum[3,3] = " << dst.query(3, 3) << '\n';
    return 0;
}

Output yang Dihasilkan:

SparseTable (min):
  min[1,5] = 1
  min[0,7] = 1
  min[3,3] = 1

DisjointSparseTable (sum):
  sum[1,5] = 20
  sum[0,7] = 36
  sum[2,4] = 12
  sum[3,3] = 4

Bedah Kode Baris-per-Baris #

1. table_.assign(K, std::vector<int>(n_)) (SparseTable): matriks K × n di mana K = floor(log2(n)) + 1. Setiap baris adalah level. Total memori O(n log n).
2. table_[0][i] = arr[i]: level 0 = elemen array itu sendiri (range length 1).
3. table_[k][i] = std::min(table_[k-1][i], table_[k-1][i + (1 << (k-1))]): gabung dua segmen berdekatan masing-masing panjang 2^(k-1) → segmen panjang 2^k.
4. log_[] array: precompute log[i] untuk semua i ∈ [0, n] agar query O(1) tanpa log() call. log[i] = log[i/2] + 1.
5. query(l, r): ambil k = log_[r-l+1] (level terbesar yang 2^k ≤ len). Hasil = min(table_[k][l], table_[k][r - 2^k + 1]). Kedua segmen [l, l+2^k-1] dan [r-2^k+1, r] overlap di tengah — karena min idempoten, tidak masalah.
6. DisjointSparseTable level 0: table_[0][i] = arr[i], sama seperti sparse table biasa.
7. Level k (k ≥ 1): step = 2^(k-1). Loop mid = step, 3*step, 5*step, ... (midpoint pada setiap blok ukuran 2*step = 2^k). Untuk setiap midpoint, isi separuh kiri [L, mid-1] dengan suffix-sum ke midpoint, dan separuh kanan [mid, R] dengan prefix-sum dari midpoint.
8. table_[k][i] di separuh kiri = sum(arr[i..mid-1]): dihitung dari kanan ke kiri. table_[k][mid-1] = arr[mid-1], lalu table_[k][i] = arr[i] + table_[k][i+1].
9. table_[k][i] di separuh kanan = sum(arr[mid..i]): dihitung dari kiri ke kanan. table_[k][mid] = arr[mid], lalu table_[k][i] = table_[k][i-1] + arr[i].
10. query(l, r): bila l == r, return elemen tunggal. Bila tidak, hitung k = 32 - __builtin_clz(l ^ r). l ^ r memberi posisi bit berbeda tertinggi — k = level di mana l dan r berada di separuh berbeda dari satu blok. Return table_[k][l] + table_[k][r] (suffix sum dari l ke midpoint + prefix sum dari midpoint ke r, tidak ada overlap).
11. Verifikasi:
    • SparseTable: arr = [7,2,3,1,5,9,4,6]. min[1,5] = min(2,3,1,5,9) = 1. min[0,7] = 1. min[3,3] = 1. ✓
    • DisjointSparseTable: arr2 = [1,2,3,4,5,6,7,8]. sum[1,5] = 2+3+4+5+6 = 20. sum[0,7] = 36. sum[2,4] = 3+4+5 = 12. sum[3,3] = 4. ✓

Kompleksitas dan Perbandingan #

Ringkasan #

• Sparse table menyimpan jawaban untuk setiap range berukuran pangkat dua.
• Standar sparse table: untuk operasi idempotent (min, max, gcd, &, |). Query O(1), build O(n log n), memori O(n log n).
• Disjoint sparse table: untuk operasi non-idempotent (sum, xor, product). Level k menyimpan prefix/suffix sum terhadap midpoint blok ukuran 2^k. Query O(1).
• Sparse table tidak mendukung update — array harus statis.
• Untuk dynamic + range query, gunakan Fenwick atau segment tree.
• Trade-off: sparse table O(1) query vs segment tree O(log n) query, tetapi sparse table O(n log n) memori dan build vs segment tree O(n).