Параллельный бинарный поиск (parallel binary search): как искать ответ сразу для всех запросов?
Есть q запросов вида «на каком наименьшем шаге t выполнится условие для запроса i», где условие проверяется через структуру (например, добавляем рёбра по времени и спрашиваем, когда две вершины соединятся). Отдельный бинпоиск на каждый запрос — O(q log n) перестроек структуры, слишком долго. Слышал про «параллельный бинпоиск» — как он устроен?
2 ответа
Параллельный бинарный поиск гоняет бинпоиск для всех q запросов одновременно, разделяя стоимость пересборки структуры. Идея: на каждой из log(n) фаз у каждого запроса есть свой текущий интервал [lo_i, hi_i] и середина mid_i. Мы один раз проходим время от 1 до n, применяя операции (добавляя рёбра/элементы), и в моменты t = mid_i отвечаем на проверку для всех запросов, чья середина = t. По результату сужаем [lo_i, hi_i] каждого. Так за один проход структуры обслуживаем все q серединок текущей фазы.
Схема:
повторить log(n) раз:
сгруппировать запросы по mid_i (например, бакеты по времени)
пересоздать/откатить структуру в начальное состояние
идём t = 1..n, применяя операцию времени t
для каждого запроса с mid_i == t: check, сузить [lo_i, hi_i]
На каждой фазе структура строится один раз за O(n · cost_op), фаз log(n), плюс обработка q проверок суммарно. Итого O((n + q) log n · cost) вместо O(q · n · log n) у наивного «бинпоиск на каждый запрос отдельно». Память O(n + q).
Применимость: проверка check(t) монотонна по t (раз выполнилось — дальше выполняется), и структуру можно строить инкрементально (DSU с откатами для «когда соединятся», дерево Фенвика для порядковых статистик и т.п.). Это и есть случай «много однотипных бинпоисков с дорогой проверкой» — параллелизация делит дорогую пересборку между всеми запросами.
Ключевая деталь реализации — как откатывать/пересобирать структуру между фазами. Два варианта: (1) строить заново с нуля на каждой фазе за O(n) — просто, если cost мал; (2) DSU с откатами (union по рангу без сжатия путей + журнал), чтобы внутри одного прохода времени двигаться монотонно вперёд и в конце фазы откатиться. Грабля: внутри одной фазы запросы нужно обрабатывать в порядке возрастания mid_i, чтобы операции применялись монотонно по времени и можно было отвечать «на лету», не перестраивая структуру для каждого запроса. Если перепутать порядок — придётся откатываться туда-сюда и вся экономия пропадёт.