RMQ $$$O(n)/O(1)$$$
ЗадачаДан массив $$$a$$$ из $$$n$$$ чисел от $$$1$$$ до $$$10^9$$$. Нужно уметь отвечать на запрос минимум на отрезке с $$$l$$$ по $$$r$$$ за $$$O(1)$$$ в онлайне и $$$O(n)$$$ предподсчета.
Для удобства будем считать, что нумерация массива с нуля.
Разобьем наш массив на блоки по $$$\lceil\log_{2}(n)\rceil$$$ чисел. Для удобства обозначим $$$bl = \lceil\log_{2}(n)\rceil$$$. В первом блоке числа с $$$a_{0}$$$ до $$$a_{bl - 1}$$$, во втором с $$$a_{bl}$$$ до $$$a_{2 * bl - 1}$$$ и так далее, в последнем блоке может быть меньше $$$bl$$$ чисел.
Таким образом, мы получили $$$\lceil\frac{n}{bl}\rceil$$$ блоков. Научимся находить минимум для отрезка, находящегося целиком внутри блока.
Будем рассматривать блоки независимо, в каждом блоке пойдем слева направо и будем поддерживать стек минимумов. Для каждой граинцы $$$r$$$ запомним стек минимумов с начала блока, в котором находится $$$r$$$, заканчивая $$$r$$$. Будем запоминать стек минимумов, как маску нулей и единиц, в $$$iм$$$ бите будет стоять $$$1$$$, если $$$iе$$$ число в блоке сейчас в стеке минимумов.
Пусть мы теперь хотим найти минимум на отрезке с $$$l$$$ до $$$r$$$, и $$$l$$$ в одном блоке с $$$r$$$. Заметим, что минимум стоит на позиции самого левого единичного бита позже $$$lго$$$(или $$$lй$$$) из стека минимума, который мы запомнили в $$$r$$$. Пусть в $$$r$$$ маска стека минимумов — $$$mask$$$. Тогда нужный нам единичный бит — первый бит в $$$mask » (l - start_{l})$$$, где $$$start_{l}$$$ — начало блока. $$$start_{l} = \lfloor\frac{l}{bl}\rfloor * bl$$$. Всего различных масок $$$2^{bl}$$$ < $$$2 * n$$$, так что с помощью динамического программирования мы можем для каждой маски предподсчитать индекс ее самого левого единичного бита.
Таким образом, мы сделали предподсчет $$$O(n)$$$ и умеем находить минимум на отрезке внутри блока. Теперь надо научиться искать минимум, если $$$l$$$ и $$$r$$$ в разных блоках. Тогда нужный нам минимум — это $$$min(getmin(l, end_{l}), getmin(start_{r}, r), getmin(end_{l} + 1, start_{r} - 1))$$$. Первые 2 величины мы умеем искать, так как границы в одном блоке, а третья величина — минимум на подотрезке блоков. Тогда, найдем минимум в каждого блоке и построим sparse table на массиве из этих минимумов. Предподсчет sparse table $$$O(\lceil\frac{n}{bl}\rceil * log_{2}(\lceil\frac{n}{bl}\rceil))$$$, то есть $$$O(n)$$$.
Мы научились за $$$O(n)$$$ предподсчета искать минимум на отрезке за $$$O(1)$$$.
При $$$n = 10^6$$$ моя реализация этого алгоритма работает столько же, сколько дерево отрезков снизу, но, скорее всего, можно реализовать лучше.
Код#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
inline int get_min_sparse_table(int l, int r, vector <vector <int>>& st, vector <int>& max_st2) {
if (l > r) return INF;
int len = r - l + 1;
return min(st[max_st2[len]][l], st[max_st2[len]][r - (1 << max_st2[len]) + 1]);
}
inline int get_min_in_block(vector <int>& a, int l, int r, vector <int>& first_bit, vector <int>& stack_min_mask, int left_block) {
return a[first_bit[(stack_min_mask[r] >> (l - left_block))] + l];
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n, m;
cin >> n >> m;
vector <int> a(n);
for (int i = 0; i < n; ++i) cin >> a[i];
int lg = (int)ceil(log2(n));
vector <int> first_bit(1 << lg);
for (int i = 0; i < lg; ++i) {
for (int mask = 1; mask < (1 << i); ++mask) {
first_bit[mask + (1 << i)] = first_bit[mask];
}
first_bit[(1 << i)] = i;
}
vector <int> all_blocks_min;
vector <int> stack_min_mask(n);
vector <int> stack_min;
for (int i = 0; i < n; i += lg) {
stack_min.clear();
int cur_min = a[i];
for (int j = i; j < min(i + lg, n); ++j) {
cur_min = min(cur_min, a[j]);
}
all_blocks_min.push_back(cur_min);
int cur_mask = 0;
for (int j = i; j < min(i + lg, n); ++j) {
while (!stack_min.empty() && a[stack_min.back()] >= a[j]) {
cur_mask -= (1 << (stack_min.back() - i));
stack_min.pop_back();
}
cur_mask += (1 << (j - i));
stack_min_mask[j] = cur_mask;
stack_min.push_back(j);
}
}
int new_len = (int)all_blocks_min.size();
int new_lg = (int)ceil(log2(new_len));
vector <vector <int>> st(new_lg, vector <int> (new_len));
for (int len = 0; len < new_lg; ++len) {
for (int start = 0; start + (1 << len) - 1 < new_len; ++start) {
if (len == 0) st[len][start] = all_blocks_min[start];
else st[len][start] = min(st[len - 1][start], st[len - 1][start + (1 << (len - 1))]);
}
}
vector <int> max_st2(new_len + 1);
for (int i = 2; i <= new_len; ++i) {
max_st2[i] = max_st2[i / 2] + 1;
}
while (m--) {
int l, r;
cin >> l >> r; --l; --r;
int block_l = l / lg, block_r = r / lg;
if (block_l == block_r) cout << get_min_in_block(a, l, r, first_bit, stack_min_mask, block_l * lg) << "\n";
else {
cout << min(min(get_min_in_block(a, l, lg * (block_l + 1) - 1, first_bit, stack_min_mask, block_l * lg),
get_min_in_block(a, block_r * lg, r, first_bit, stack_min_mask, block_r * lg)),
get_min_sparse_table(block_l + 1, block_r - 1, st, max_st2)) << "\n";
}
}
}
Улучшенная версия этого алгоритма, поддерживающая изменения
ЗадачаДан массив $$$a$$$ из $$$n$$$ чисел от $$$1$$$ до $$$10^9$$$. Нужно уметь отвечать на запрос минимум на отрезке с $$$l$$$ по $$$r$$$ и уметь делать $$$a_{i} = x$$$.
Недавно я задумался, как можно изменять эту структуру и придумал, что вместо sparse table на минимумах в блоках, можно еще раз разбить на блоки по $$$log_{2}(n)$$$, посчитать стеки минимумов и снова сделать ту же структру. Фактически, будем несколько уровней структуры, на каждом надо поддерживать нужные маски и размеры блоков. Будем сокращать длину следующего уровня до тех пор, пока количество чисел на уровне больше $$$2$$$. На каждом уровне количество чисел сокращается в $$$log_{2}(len)$$$, где $$$len$$$ — длина массива на последнем уровне. На каждом уровне предподсчет линеен.
Таким образом, пусть $$$f(n) = f(\lceil\frac{n}{\lceil\log_{2}(n)\rceil}\rceil) + n$$$, тогда на предподсчет нужно $$$O(f(n))$$$.
Рассмотрим запрос обновления: У нас изменится стек минимумов в одном блоке на самом длиннов уровне, так что пересчитаем его в тупую, затем может измениться минимум в блоке, так что надо пересчитать стек минимумов в одном блоке на уровне выше и так далее. Таким образом, пусть $$$g(n) = g(\lceil\frac{n}{\lceil\log_{2}(n)\rceil}\rceil) + \log_{2}(n)$$$, тогда на запрос обновления $$$O(g(n))$$$.
Рассмотрим запрос минимума на отрезке: Если границы в одном блоке на самом длинном уровне, то просто найдем ответ. Иначе, нам надо найти минимум в маленьком подотрезке слева(за $$$O(1)$$$, в маленьком подтрезке справа(за $$$O(1)$$$) и на подотрезке из блоков. Таким образом, пусть $$$t(n) = t(\lceil\frac{n}{\lceil\log_{2}(n)\rceil}\rceil) + 1$$$, тогда на запрос минимума на отрезке $$$O(t(n))$$$.
Получается, операция update дольше $$$O(log_{2}(n))$$$, но быстрее $$$O(log_{2}(n)^2)$$$(так как уровней не больше $$$log_{2}(n)$$$ и на каждом длина блока не больше $$$log_{2}(n)$$$. Более точную оценку я дать не могу.
Операция get быстрее $$$O(log_{2}(n))$$$, так как каждый раз длина уровня сокращается не меньше, чем в $$$2$$$ раза. Опять же, я не знаю как это оценить точнее, но я провел тесты.
При $$$n = 10^6$$$, эта структра работает в среднем $$$1250мс$$$, рекурсивное дерево отрезков $$$850мс$$$, дерево отрезков снизу $$$680мс$$$.
Когда запросов get в $$$100$$$ раз больше, чем запросов update, эта структра работает в среднем $$$1170мс$$$, рекурсивное дерево отрезков $$$1600мс$$$, дерево отрезков снизу $$$1200мс$$$. Не знаю, почему время работы моей структуры не сильно изменилось, скорее всего из-за константы, но по идее должно работать сильно быстрее, так как при $$$n = 10^6$$$, $$$t(n) = 6$$$, $$$g(n) = 65$$$. $$$f(n) = 1053421$$$, что почти $$$10^6$$$. Тесты, которые я делал рандомные.
Код#include <bits/stdc++.h>
using namespace std;
int INF = 1e9;
signed main() {
if (1) {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
}
int n, m;
cin >> n >> m;
vector <int> a(n);
for (int i = 0; i < n; ++i) cin >> a[i];
vector <int> block_sizes;
vector <vector <int>> all_levels_values;
vector <vector <int>> all_stack_min_masks;
int max_lg = (int)ceil(log2(n));
vector <int> pre_calc((1 << max_lg));
for (int i = 0; i < max_lg; ++i) {
for (int mask = 1; mask < (1 << i); ++mask) {
pre_calc[mask + (1 << i)] = pre_calc[mask];
}
pre_calc[1 << i] = i;
}
all_levels_values.push_back(a);
block_sizes.push_back(max_lg);
while (true) {
all_stack_min_masks.push_back({});
for (int i = 0; i < all_levels_values.back().size(); i += block_sizes.back()) {
int cur_mask = 0;
vector <int> stack_min;
for (int j = i; j < min((int)all_levels_values.back().size(), i + block_sizes.back()); ++j) {
while (!stack_min.empty() && all_levels_values.back()[stack_min.back()] >= all_levels_values.back()[j]) {
cur_mask -= (1 << (stack_min.back() - i));
stack_min.pop_back();
}
stack_min.push_back(j);
cur_mask += (1 << (j - i));
all_stack_min_masks.back().push_back(cur_mask);
}
}
if (all_levels_values.back().size() > 1) {
vector <int> now = all_levels_values.back();
all_levels_values.push_back({});
for (int i = 0; i < now.size(); i += block_sizes.back()) {
int minn = now[i];
for (int j = i; j < min((int)now.size(), i + block_sizes.back()); ++j) minn = min(minn, now[j]);
all_levels_values.back().push_back(minn);
}
block_sizes.push_back(max((int)ceil(log2((int)all_levels_values.back().size())), 2));
} else break;
}
while (m--) {
int type;
cin >> type;
if (type == 1) {
int i, x;
cin >> i >> x; --i;
for (int lvl = 0; lvl < (int)all_levels_values.size(); ++lvl) {
all_levels_values[lvl][i] = x;
int start = i / block_sizes[lvl] * block_sizes[lvl];
vector <int> stack_min;
int cur_mask = 0, minn = INF;
for (int j = start; j < min((int)all_levels_values[lvl].size(), start + block_sizes[lvl]); ++j) {
while (!stack_min.empty() && all_levels_values[lvl][stack_min.back()] >= all_levels_values[lvl][j]) {
cur_mask -= (1 << (stack_min.back() - start));
stack_min.pop_back();
}
minn = min(minn, all_levels_values[lvl][j]);
stack_min.push_back(j);
cur_mask += (1 << (j - start));
all_stack_min_masks[lvl][j] = cur_mask;
}
x = minn;
i /= block_sizes[lvl];
}
} else {
int l, r;
cin >> l >> r; --l; --r;
if (l == 0 && r == n - 1) {
cout << all_levels_values.back().back() << "\n";
continue;
}
int minn = INF;
for (int lvl = 0; lvl < (int)all_levels_values.size(); ++lvl) {
if (l > r) break;
int start_l = l / block_sizes[lvl] * block_sizes[lvl];
int start_r = r / block_sizes[lvl] * block_sizes[lvl];
if (start_l == start_r) {
int new_mask = (all_stack_min_masks[lvl][r] >> (l - start_l));
int ans = all_levels_values[lvl][start_l + pre_calc[new_mask] + l - start_l];
minn = min(minn, ans);
break;
}
int new_mask = (all_stack_min_masks[lvl][start_l + block_sizes[lvl] - 1] >> (l - start_l));
minn = min(minn, all_levels_values[lvl][start_l + pre_calc[new_mask] + l - start_l]);
new_mask = all_stack_min_masks[lvl][r];
minn = min(minn, all_levels_values[lvl][start_r + pre_calc[new_mask]]);
l /= block_sizes[lvl];
r /= block_sizes[lvl];
++l;
--r;
}
cout << minn << "\n";
}
}
}