Sparse nloglogn

Другие решения

Многим известен алгоритм Sparse table, который работает за O(n log n) на построение и O(1)на запрос и решает задачу static RMQ. Так же эту задачу решает алгоритм ФКБ за O(n) на построение и O(1) на запрос, но при этом имеет неприлично большую константу и неприятен в написании. В следствии чего ФКБ мало применим в олимпиадных задачах.

Идея 1

Построение

Разобьём массив, на котором мы будем отвечать на запросы на блоки по logn, в каждом из блоков построим обычный sparse table за O(lognloglogn) количество таких блоков = n/logn => суммарно эти построения будут выполнены за O(nloglogn). В каждом блоке посчитаем минимум и на этих минимумах построим также sparse за O((n/logn) * log(n / logn)) <= O(n).

Ответ на запрос

Заметим, что если левая(l) и правая(r) границы запроса полностью лежат в одном блоке, то мы можем ответить за O(1) за счёт насчитанного в блоке Sparse table, если же l и r в разных блоках то введем l1 = (l / logn) + 1, r1 = (r / logn) — 1. Очевидно что ответ будет минимум из минимума на суффиксе блока l и префиксе блока r, и минимума на вех блоках с номерами с [l1 : r1] => ответ на запрос происходит за O(1)

Код

template<typename T>
struct sparse_table {
    vector<vector<T>> sparse;
    vector<ll> logs;
    ll n;
 
    void init_logs() {
        logs.resize(n + 1);
        logs[1] = 0;
        for (ll i = 2; i <= n; i++) {
            logs[i] = logs[i / 2] + 1;
        }
    }
 
    T get_max(ll l, ll r) {
        ll n_l = min(l, r);
        ll n_r = max(l, r);
        ll k = logs[n_r - n_l + 1];
        return min(sparse[k][n_l], sparse[k][n_r - (1 << k) + 1]).second;
    }
 
    void init(vector<T>& a) {
        n = a.size();
        init_logs();
        sparse.resize(logs[n] + 1, vector<T>(n));
        sparse[0] = a;
        for (ll k = 1; k <= logs[n]; k++) {
            for (ll i = 0; i + (1 << (k - 1)) < n; i++) {
                sparse[k][i] = min(sparse[k - 1][i], sparse[k - 1][i + (1 << (k - 1))]);
            }
        }
    }
};
 
template<typename T>
struct fast_sparse_table {
    vector<sparse_table<T>> for_st;
    sparse_table<T> blocks;
    int bs = 1;
 
    T get_max(ll l, ll r) {
        if (l > r) {
            swap(l, r);
        }
        if (r / bs == l / bs) {
            return for_st[l / bs].get_max(l % bs, r % bs);
        }
        ll minim = for_st[l / bs].get_max(l % bs, bs - 1);
        minim = min(minim, for_st[r / bs].get_max(0, r % bs));
        if (r / bs - 1 >= l / bs + 1) {
            minim = min(minim, blocks.get_max(l / bs + 1, r / bs - 1));
        }
        return minim;
    }
 
    void init(vector<T>& a) {
        ll tz = 1;
        while (tz < a.size()) {
            tz *= 2;
            ++bs;
        }
        vector<T> f_b(a.size() / bs + 1, {1e9, -1});
        for_st.resize(a.size() / bs + 1);
        vector<T> temp;
        for (int i = 0; i < int(a.size()); i++) {
            f_b[i / bs] = min(f_b[i / bs], a[i]);
            temp.push_back(a[i]);
            if (i % bs == bs - 1) {
                for_st[i / bs].init(temp);
                temp.clear();
            }
        }
        blocks.init(f_b);
        if (temp.size() != 0) {
            for_st[(a.size() - 1) / bs].init(temp);
        }
    }
};

Масштабируемость

Логичный вопрос почему мы не можем продолжать делить на блоки, а на блоках строить более быструю sparse table, с вот таким примерным кодом

template <typename T, int level>
struct sparse_table {
    vector<sparse_table<T, level - 1>> for_st;
    sparse_table<T, 1> blocks;
    int bs = 1;
 
    T get_max(ll l, ll r) {
        if (r / bs == l / bs) {
            return for_st[l / bs].get_max(l % bs, r % bs);
        }
        T minim = for_st[l / bs].get_max(l % bs, bs - 1);
        minim = min(minim, for_st[r / bs].get_max(0, r % bs));
        if (r / bs - 1 >= l / bs + 1) {
            minim = min(minim, blocks.get_max(l / bs + 1, r / bs - 1));
        }
        return minim;
    }
 
    void init(vector<T>& a) {
        ll tz = 1;
        while (tz < a.size()) {
            tz *= 2;
            bs++;
        }
        vector<T> f_b(a.size() / bs + 1);
        for_st.resize(a.size() / bs + 1);
        vector<T> temp;
        for (int i = 0; i < int(a.size()); i++) {
            if (i % bs == 0) {
                f_b[i / bs] = a[i];
            }
            f_b[i / bs] = min(f_b[i / bs], a[i]);
            temp.push_back(a[i]);
            if (i % bs == bs - 1) {
                for_st[i / bs].init(temp);
                temp.clear();
            }
        }
        blocks.init(f_b);
        if (temp.size() != 0) {
            for_st[(a.size() - 1) / bs].init(temp);
        }
    }
};
 
 
template <typename T>
struct sparse_table<T, 1> {
    vector<vector<T>> sparse;
    vector<ll> logs;
    ll n;
 
    void init_logs() {
        logs.resize(n + 1);
        logs[1] = 0;
        for (ll i = 2; i <= n; i++) {
            logs[i] = logs[i / 2] + 1;
        }
    }
 
    T get_max(ll l, ll r) {
        ll n_l = min(l, r);
        ll n_r = max(l, r);
        ll k = logs[n_r - n_l + 1];
        return min(sparse[k][n_l], sparse[k][n_r - (1 << k) + 1]);
    }
 
    void init(vector<T>& a) {
        n = a.size();
        init_logs();
        sparse.resize(logs[n] + 1, vector<T>(n));
        sparse[0] = a;
        for (ll k = 1; k <= logs[n]; k++) {
            for (ll i = 0; i + (1 << (k - 1)) < n; i++) {
                sparse[k][i] = min(sparse[k - 1][i], sparse[k - 1][i + (1 << (k - 1))]);
            }
        }
    }
};

Но появляется несколько проблем, ответ на запрос теперь работает за O(2 ^ (level — 1)) и построение работает за O(nlog...log(level раз) n + level * n) из этого очевидно что максимальный level, который даёт хоть какое преимущество перед ДО, это level = 2, но также стоит заметить, что при level > 4 константа на запрос сильно возрастает и эта вариация sparse table становится примерно бесполезной, т.к. работает хуже чем обычная sparse table в ответах на запросах, и хуже чем ДО в построение.

Идея 2

Заметим, что на запросы запросы на суффиксе и префиксе можно отвечать за O(level), но притом построение начнёт работать за O(3 * (level — 1) * n + n loglog(level раз)n), что имеет те же проблемы, что и прошлая идея, и притом потребляет больше памяти, хоть и быстрее отвечает на запрос

Благодарность

Отдельное спасибо хочется выразить systy