Sparse nloglogn↵
================↵
Другие решения↵
--------↵
Многим известен алгоритм [Sparse table](https://mirror.codeforces.com/blog/entry/101083), который работает за 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 = loglogn, но также стоит заметить, что при level > 4 константа на запрос сильно возрастает и эта вариация sparse table становится примерно бесполезной, т.к. работает хуже чем обычная sparse table в ответах на запросах, и хуже чем ДО в построение.↵
### Идея 2↵
Заметим, что на запросы запросы на суффиксе и префиксе можно отвечать за O(level), но притом построение начнёт работать за O(3 * (level — 1) * n + n loglog(level раз)n), что имеет те же проблемы, что и прошлая идея, и притом потребляет больше памяти, хоть и быстрее отвечает на запрос↵
↵
↵
↵
↵
↵
↵
================↵
Другие решения↵
--------↵
Многим известен алгоритм [Sparse table](https://mirror.codeforces.com/blog/entry/101083), который работает за 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 = loglogn, но также стоит заметить, что при level > 4 константа на запрос сильно возрастает и эта вариация sparse table становится примерно бесполезной, т.к. работает хуже чем обычная sparse table в ответах на запросах, и хуже чем ДО в построение.↵
### Идея 2↵
Заметим, что на запросы запросы на суффиксе и префиксе можно отвечать за O(level), но притом построение начнёт работать за O(3 * (level — 1) * n + n loglog(level раз)n), что имеет те же проблемы, что и прошлая идея, и притом потребляет больше памяти, хоть и быстрее отвечает на запрос↵
↵
↵
↵
↵
↵
↵
