Sparse table
Ελάχιστο σε διάστημα στατικού πίνακα σε , μετά από προεπεξεργασία .
Πότε
Ο πίνακας δεν αλλάζει και τα ερωτήματα είναι πάρα πολλά, ή το ερώτημα βρίσκεται μέσα σε άλλον βρόχο (π.χ. μέσα σε δυαδική αναζήτηση), οπότε το του segment tree μετράει.
Η ιδέα
. Το επίπεδο φτιάχνεται από το με δύο μισά: .
Για ερώτημα με μήκος , πάρε . Τα δύο μπλοκ μήκους , ένα από την αρχή και ένα από το τέλος, καλύπτουν όλο το διάστημα. Επικαλύπτονται, αλλά αυτό δεν πειράζει για το ελάχιστο:
Το ίδιο ισχύει για κάθε πράξη με : μέγιστο, gcd, and, or. Όχι για άθροισμα, όπου η επικάλυψη μετριέται δύο φορές.
Παγίδες
- Υπολόγισε τους λογαρίθμους μία φορά σε πίνακα (
lg[i] = lg[i / 2] + 1), όχι μεlog2σε double μέσα στο ερώτημα. - Μνήμη : για είναι περίπου τιμές, δηλαδή 29 MB σε
long long. Αν το όριο είναι 256 MB είσαι άνετος· σε 64 MB πρόσεξε.
Κώδικας
Χωρίς main: μπαίνει κάτω από τα #include, το using namespace std και το using ll = long long.
// 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
Με τη σειρά: το πρώτο είναι η καθαρή εφαρμογή, τα επόμενα θέλουν μια παραλλαγή.
- Static Range Minimum Queries · Range Queries