Set за O(1) на вставку и корень на взятие минимума

Материал из Algocode wiki
Версия от 15:41, 2 декабря 2021; Tikhon (обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

std::set

Обычный std::set умеет выполнять операции:

  • insert(x)
  • erase(x)
  • get_min() - оно же *s.begin()

на других его возможностях пока останавливаться не будем. Все эти операции set делает за O($\log_2{n}$), Так что если к set поступит:

  • $q_1$ запросов $insert / erase$
  • $q_2$ запросов get_min

- то он отрабоает за $O((q_1 + q_2) \cdot \log_2{n})$

- А что если $q_1$ сильно больше $q_2$, например $q_1 = \sqrt{n} \cdot q_2$, можно ли чем-то заменить set, чтобы он работал быстрее?

Прокачиваем set

Для начала будем считать, что для для всех запросов insert(x) $x \le N$ для некоторого $N$. Потом подумаем, что делать с большими числами

Давайте воспользуемся классической корневой декомпозицией:

  • заведем массив $cnt[N]$, в котором в индексе $i$ будет количество чисел, равных i в нашем "$set$" (если нам нужен именно set, а не multiset, то $cnt[i] = 0/1$)
  • разделим этот массив на блоки длины $C$, и для каждого блока сохраним сумму $cnt[i]$ в этом блоке
  • при операциях insert / erase поддерживать массив $cnt$ и суммы в блоках за $O(1)$ очень просто - просто +-1 в соответствующих ячейках
  • Чтобы ответить на запрос get_min, пройдем по блокам, пока не найдем такой, что сумма в нем $\neq$ 0, а по нему пройдемся честно. Это сработает за $O(\sqrt{N})$

- итого на те же самые $q_1$ запросов insert/erase и $q_2$ запросов get_min мы ответим за $O(q_1 + q_2 \cdot \sqrt{N})$

- чтобы решить проблему с тем, что числа, добавленные в set могут быть слишком большими, можем воспользоваться алгоритмом сжатие координат

- Заметим, что такой "set" легко обобщается на более сложные, чем get_min, операции, например можно сделать $k$-й минимум без изменения асимптотики

- Эта идея бывает очень полезна при реализации Алгоритм Мо, так как там запростов изменения примерно в $\sqrt{n}$ раз больше, чем запросов оперции




Автор конспекта: Евтеев Тихон

По всем вопросам пишите в telegram @tikhon282