uniolympiads English

Sparse table

Ελάχιστο σε διάστημα στατικού πίνακα σε O(1)O(1), μετά από προεπεξεργασία O(nlog⁡n)O(n \log n).

Πότε

Ο πίνακας δεν αλλάζει και τα ερωτήματα είναι πάρα πολλά, ή το ερώτημα βρίσκεται μέσα σε άλλον βρόχο (π.χ. μέσα σε δυαδική αναζήτηση), οπότε το log⁡n\log n του segment tree μετράει.

Η ιδέα

stk[i]=min⁡(ai,…,ai+2k−1)\mathrm{st}_k[i] = \min(a_i, \dots, a_{i + 2^k - 1}). Το επίπεδο kk φτιάχνεται από το k−1k-1 με δύο μισά: stk[i]=min⁡(stk−1[i],stk−1[i+2k−1])\mathrm{st}_k[i] = \min(\mathrm{st}_{k-1}[i], \mathrm{st}_{k-1}[i + 2^{k-1}]).

Για ερώτημα [l,r][l, r] με μήκος L=r−l+1L = r - l + 1, πάρε k=⌊log⁡2L⌋k = \lfloor \log_2 L \rfloor. Τα δύο μπλοκ μήκους 2k2^k, ένα από την αρχή και ένα από το τέλος, καλύπτουν όλο το διάστημα. Επικαλύπτονται, αλλά αυτό δεν πειράζει για το ελάχιστο:

min⁡(al,…,ar)=min⁡(stk[l], stk[r−2k+1]).\min(a_l, \dots, a_r) = \min\bigl(\mathrm{st}_k[l],\ \mathrm{st}_k[r - 2^k + 1]\bigr).

Το ίδιο ισχύει για κάθε πράξη με x∘x=xx \circ x = x: μέγιστο, gcd, and, or. Όχι για άθροισμα, όπου η επικάλυψη μετριέται δύο φορές.

Παγίδες

  • Υπολόγισε τους λογαρίθμους μία φορά σε πίνακα (lg[i] = lg[i / 2] + 1), όχι με log2 σε double μέσα στο ερώτημα.
  • Μνήμη nlog⁡nn \log n: για n=2⋅105n = 2 \cdot 10^5 είναι περίπου 3.6⋅1063.6 \cdot 10^6 τιμές, δηλαδή 29 MB σε long long. Αν το όριο είναι 256 MB είσαι άνετος· σε 64 MB πρόσεξε.

Κώδικας

Χωρίς main: μπαίνει κάτω από τα #include, το using namespace std και το using ll = long long.

cpp/sparse-table.cpp
// Sparse table for range minimum on a static array.
// Build O(n log n), query O(1): [l, r] is covered by two overlapping blocks of length 2^k.
// Works for any idempotent operation (min, max, gcd), not for sums.

struct SparseTable {
    vector<vector<ll>> st;
    vector<int> lg;

    SparseTable(const vector<ll>& a) {
        int n = a.size();
        lg.assign(n + 1, 0);
        for (int i = 2; i <= n; i++) {
            lg[i] = lg[i / 2] + 1;
        }
        int levels = lg[max(n, 1)] + 1;
        st.assign(levels, vector<ll>(n));
        for (int i = 0; i < n; i++) {
            st[0][i] = a[i];
        }
        for (int k = 1; k < levels; k++) {
            for (int i = 0; i + (1 << k) <= n; i++) {
                st[k][i] = min(st[k - 1][i], st[k - 1][i + (1 << (k - 1))]);
            }
        }
    }

    ll query(int l, int r) {
        int k = lg[r - l + 1];
        return min(st[k][l], st[k][r - (1 << k) + 1]);
    }
};

Ελέγχθηκε σε 1.000 τυχαίες περιπτώσεις απέναντι σε αργή, προφανώς σωστή λύση, με AddressSanitizer και UndefinedBehaviorSanitizer (g++ (Ubuntu 13.3.0-6ubuntu2~24.04.1) 13.3.0, 2026-11-18 23:27 UTC).

Για εξάσκηση στο CSES

Με τη σειρά: το πρώτο είναι η καθαρή εφαρμογή, τα επόμενα θέλουν μια παραλλαγή.