RMQ $$$O(n)/O(1)$$$
Для удобства будем считать, что нумерация массива с нуля.
Разобьем наш массив на блоки по $$$\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$$$ моя реализация этого алгоритма работает столько же, сколько дерево отрезков снизу, но, скорее всего, можно реализовать лучше.
Улучшенная версия этого алгоритма, поддерживающая изменения
Недавно я задумался, как можно изменять эту структуру и придумал, что вместо 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$$$. Тесты, которые я делал рандомные.
Автокомментарий: текст был обновлен пользователем daubi (предыдущая версия, новая версия, сравнить).
Auto comment: topic has been updated by daubi (previous revision, new revision, compare).
Finally, an educational blog that makes sense to me. Thanks!!
Auto comment: topic has been updated by daubi (previous revision, new revision, compare).
Auto comment: topic has been updated by daubi (previous revision, new revision, compare).
Автокомментарий: текст был обновлен пользователем daubi (предыдущая версия, новая версия, сравнить).
This happens and tutorial comes out.. what are the odds though :P
First part of this blog is described in https://mirror.codeforces.com/blog/entry/78931.
Here's my code for the static data structure above. It's not perfect, but it's pretty fast.
As for the dynamic structure. $$$f(n)$$$ is obv linear. My scientific guess is that $$$g(n)=log(n)\cdot t(n)$$$ and $$$t(n)=log^*(n)$$$.
Yes, thanks, I agree about linearity of $$$f(n)$$$, but the second statement does not work if you take a large enough $$$n$$$ and look at these functions.
FWIW, the number of 'levels' $$$t(n)$$$ is $$$\Theta(\frac{\log{n}}{\log{\log{n}}})$$$, and likewise $$$g(n)$$$ is in $$$\Theta(\frac{(\log{n})^2}{\log{\log{n}}})$$$.
It's easy to see that it can't be much smaller, since the blocks at each level are at most $$$\lceil\log{n}\rceil$$$ times larger than the blocks on the next smaller level and the sizes span the whole $$$[1..n]$$$ range.
To get an upper bound you can first consider the levels spanning the $$$[\sqrt{n} .. n]$$$ range. Their ratios are at least $$$\log{\sqrt{n}} = \frac{1}{2} \log{n}$$$, so there are at most $$$1 + \frac{\log{\frac{n}{\sqrt{n}}}}{\log{\log{\sqrt{n}}}}$$$ of them, meaning that $$$t(n) \leq t(\sqrt{n}) + 1 + \frac{\log{\frac{n}{\sqrt{n}}}}{\log{\log{\sqrt{n}}}}$$$. Since this difference is around $$$\frac{\log{n}}{2 \log{\log{n}}}$$$ for large $$$n$$$, and that is comparable to the difference between $$$\frac{\log{n}}{\log{\log{n}}}$$$ and $$$\frac{\log{\sqrt{n}}}{\log{\log{\sqrt{n}}}}$$$ (also for large enough $$$n$$$), it is pretty standard to prove the upper bound by induction using this estimate.
For g's complexity, going from $$$n$$$ to $$$\sqrt{n}$$$ adds $$$\mathcal{O}\left(\log_2(n) \log_{\log_2(n)}(n)\right)$$$ or $$$\frac{\log_2(n)^2}{\log_2 \log_2(n)}$$$. Note that $$$\log_2(\sqrt{n}) = \frac{1}{2} \log_2(n)$$$, so the next term $$$\frac{\log_2(\sqrt{n})^2}{\log_2 \log_2(\sqrt{n})}$$$ is at most $$$\frac{1}{2}$$$ the first term. Thus, the complexity is $$$\mathcal{O}\left(\frac{\log_2(n)^2}{\log_2 \log_2(n)}\right)$$$. Similarly, the complexity of t is $$$\mathcal{O}\left(\frac{\log_2(n)}{\log_2 \log_2(n)}\right)$$$.
Edit: sniped :)