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
