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

Предпосылки

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

Мотивация

Наша цель — решить задачу Метеоры. Она звучит так:

Дан массив длины $$$M$$$, раскрашенный в $$$N$$$ цветов. Поступает $$$Q$$$ последовательных запросов прибавления значения на отрезках. Необходимо, чтобы в ячейках цвета $$$i$$$ сумма всех значений была равна как минимум $$$req[i]$$$. Для каждого цвета нужно определить момент, в который будет набрана требуемая сумма.

Решение

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

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

Давайте делать эти $$$N$$$ бинарных поисков несколько по-другому.

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

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

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

Реализация

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

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

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

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

Псевдо код

for all logQ steps:
    clear range tree and linked list check
    for all colors 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 colors m in check[q]:
            if m has requirements fulfilled:
                R[m] = q
            else:
                L[m] = q + 1

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

Тут можно найти AC решение автора оригинальной статьи. Стоит отметить,что в нем вместо ДО используется дерево Фенвика — это делает код быстрее.