Простой метод rmq O(n)/O(1) и его улучшенная версия, поддерживающая изменения

Revision ru1, by daubi, 2021-06-28 16:57:41

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$$$ моя реализация этого алгоритма работает столько же, сколько дерево отрезков снизу, но, скорее всего, можно реализовать лучше.

Код

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru10 Russian daubi 2021-06-28 23:55:24 23
en4 English daubi 2021-06-28 23:54:56 23
en3 English daubi 2021-06-28 23:33:05 40
en2 English daubi 2021-06-28 23:05:49 0 (published)
en1 English daubi 2021-06-28 23:05:08 13430 Initial revision for English translation (saved to drafts)
ru9 Russian daubi 2021-06-28 18:23:24 0 (опубликовано)
ru8 Russian daubi 2021-06-28 18:17:25 2 Мелкая правка: 'для отрезки, находяще' -> 'для отрезка, находяще'
ru7 Russian daubi 2021-06-28 17:50:34 2 Мелкая правка: 'л тесты.\nПри $n =' -> 'л тесты.\n\nПри $n ='
ru6 Russian daubi 2021-06-28 17:49:09 0 Мелкая правка: '$. Не знаю, почему вр' -> '$. Не знаю? почему вр'
ru5 Russian daubi 2021-06-28 17:48:17 1 Мелкая правка: 'чти $10^6$\nТесты, к' -> 'чти $10^6$.\nТесты, к'
ru4 Russian daubi 2021-06-28 17:47:31 639
ru3 Russian daubi 2021-06-28 17:36:12 6911 Мелкая правка: 'rceil) + n\n' -> 'rceil) + n$\n'
ru2 Russian daubi 2021-06-28 17:01:36 8
ru1 Russian daubi 2021-06-28 16:57:41 5565 Первая редакция (сохранено в черновиках)