Оригинальная статья

Предпосылки

Бинарный поиск — как он работает и где его можно применить!

Мотивация

Наша цель — решить задачу Метеоры. Она звучит так: Дано $$$N$$$ государств и $$$M$$$ секторов. Каждый сектор принадлежит некоторому государству. Есть $$$Q$$$ запросов, указывающих величину метеоритного дождя на секторах из отрезка $$$[L, R]$$$ в данный день. Государство с номером $$$i$$$ хочет набрать $$$reqd[i]$$$ метеоров со всех своих секторов. Какое минимальное количество дней должно ждать каждое из государств, чтобы собрать необходимое количество метеоров?

Решение

Наивное решение — бинарным поиском найти ответ для всех государств по отдельности. Вычисляя новое значение $$$mid$$$, будем применять запросы до него и смотреть, достаточно ли текущему государству количества метеоров, выпавшего на протяжении $$$mid$$$ дней. Для такого решения нужно уметь прибавлять значение на отрезках, это можно сделать с помощью дерева отрезков с ленивым проталкиванием. Таким образом, мы получим сложность $$$O(N * \log{}Q * Q * \log{}M)$$$, но это слишком много для ограничения по времени данной задачи.

Давайте посмотрим, не делаем ли мы лишних действий. Заметим, что во время всех бинарных поисков мы несколько раз заново применяем запросы до некоторой точки. Например, первое значение $$$mid$$$ одинаково для всех государств, но мы без необходимости вычисляем количество метеоров, выпавшее на протяжении $$$mid$$$ дней на всех секторах, для каждого государства снова и снова, хотя могли бы каким-то образом кэшировать результат.

Давайте делать эти $$$N$$$ бинарных поисков несколько по-другому. На каждом шаге будем сгруппировывать государства по состоянию диапазонов их бинарного поиска. Далее будем применять все $$$Q$$$ запросов последовательно и смотреть, не является ли текущий запрос значением $$$mid$$$ для некоторой группы государств. Если является, то пройдемся по этим государствам, проверим для них необходимые условия и обновим их диапазон поиска. Так, на первом шаге все государства лежат в диапазоне $$$[1, Q]$$$, их значение $$$mid$$$ — $$$Q / 2$$$. На втором шаге кто-то будет лежать в $$$[1, Q/2]$$$, а кто-то — в $$$[Q/2, Q]$$$ в зависимости от того, был ли верен предикат бинарного поиска. На третьем шаге государства будут находиться в диапазонах $$$[1, Q / 4]$$$, $$$[Q / 4, Q / 2]$$$, $$$[Q / 2, 3Q / 4]$$$, $$$[3Q / 4, Q]$$$. Таким образом, после $$$\log{}Q$$$ шагов каждый диапазон выродится в точку, обозначающей ответ для некоторого государства. Это намного эффективней, так как теперь нам достаточно сделать $$$Q * \log{}Q$$$ применений запросов, вместо $$$N * Q * \log{}Q$$$. Каждое применение требует $$$O(\log{}M)$$$ времени, так что теперь мы решаем задачу за $$$O(Q * \log{}Q * \log{}M)$$$.

"Отличный способ визуализировать это — представить дерево бинарного поиска. Предположим, мы выполняем стандартный бинарный поиск, и нам нужно сузиться до левого интервала — об этом можно думать, как о спуске влево в дереве. И наоборот, если нужно сузиться до правого интервала — спускаемся вправо.

Параллельный бинарный поиск за один шаг делает так же: он спускается по N деревьев бинарного поиска одновременно, требуя $$$O(N * X)$$$ времени, где $$$X$$$ зависит от задачи и структуры данных, используемой для ее решения. Поскольку высота каждого дерева — $$$O(\log{}N)$$$, получаем сложность $$$O(N * X * \log{}N)$$$." — animeshf

Реализация

Для реализации нам необходимы следующие структуры данных:

1. связный список для каждого государства, хранящий принадлежащие им сектора.
2. массивы $$$L$$$ и $$$R$$$, указывающие диапазон бинарного поиска для каждого государства.
3. структура данных для обновления на отрезках(ДО).
4. связный список $$$check$$$ для каждого значения $$$mid$$$ текущих диапазонов бинарного поиска. В $$$check[mid]$$$ храним номера государств, для которых $$$mid$$$ — это середина их диапазона.

Реализация довольно проста. На каждом из $$$\log{}Q$$$ шагов мы делаем следующее:

1. очищаем ДО и список $$$check$$$.
2. проходимся по всем государствам и добавляем их номера в нужный список $$$check[mid]$$$.
3. последовательно применяем запросы и сморим, пуст ли связный список $$$check$$$ для текущего запроса или нет. Если не пуст, то проходим по всем государствам в этом списке и обновляем диапазон их бинарного поиска.

Псевдо код

for all logQ steps:
    clear range tree and linked list check
    for all member states i:
        if L[i] != R[i]:
            mid = (L[i] + R[i]) / 2
            insert i in check[mid]
    for all queries q:
        apply(q)
        for all member states m in check[q]:
            if m has requirements fulfilled:
                R[m] = q
            else:
                L[m] = q + 1

Функция $$$apply()$$$ применяет текущий запрос, то есть прибавляет значение на отрезке в ДО. Так же, чтобы проверить, что все условия для некоторого государства выполнены, нужно пройтись по принадлежащим ему секторам и найти сумму.