Дано корневое дерево, необходимо находить наименьшего общего предка пары вершин за \(O( \log{n})\).
Давайте возьмем самую глубокую вершину из нашей пары и передвинем ее вверх так, чтобы новая глубина обоих вершин совпадала. Пока просто допустим, что мы умеем делать это быстро.
Если вершины совпадают - можно сразу вернуть эту вершину. В противном случае давайте будем поднимать на один ход обе вершины и выписывать \(0\), если они не совпадают и \(1\), если совпадают, пока не достигнем корня.
Заметим монотонность: в какой-то момент вершины станут совпадать и это будет продолжаться до самого корня. Значит можно применить бинпоиск!
Опять встает проблема: непонятно как проверять условие бинпоиска. Если немного подумать станет очевидно, что нам опять, как в начале нужна функция, умеющая нас поднимать вверх на дереве на сколько-то вершин.
Давайте назовем такую функцию kth_anc(v,k), которая возвращает \(k\)-го предка вершины \(v\).
Вспомним, что любое число \(n\) можно разбить на \(O(\log{n})\) степеней двойки.
Давайте предподсчитаем для каждой вершины \(v\) каждого \(2^i\)-го предка, как \(binup[v][i]\) (если не существует \(2^i\)-го предка - вернем корень).
Теперь взглянем на двоичную запись числа \(k\) (на сколько нужно прыгнуть вверх). Где стоят единицы - значит там есть нужная нам степень двойки. Пройдемся по всем этим степеням и прыгнем ровно на эту степень.
Итак, kth_anc(v,k) работает за \(O(\log{n})\). Плюс еще бинпоиск. Итого, \(O(\log^2{n})\).
Заметим, что когда мы производим подъем по степеням двойки мы можем сразу понять что мы идем в общего предка. Тогда давайте модифицируем алгоритм: будем переходить на максимальное \(2^i\), такое что \(binup[u][i] \ne binup[v][i] \). Если такого \(i\) не существует, значит предок эти вершин и есть ответ.
Дан массив неотрицательных чисел \(a_1, a_2 ... a_n\)и \(q\) запросов: для \(l, x, (1 \le l \le n) \) найти минимальное \(r\), что \(a_l + a_{l+1} ... + a_r \ge x\).
Опять заметим монотонность: если мы можем взять \(r\), то можно взять \(r+1\). Если есть структура умеющая считать сумму за \(O(1)\) уже можно писать бинпоиск. Но мы можем взять вместо суммы максимум, например.
Нам нужно что-то умеющее опять-таки считать значение на степени двойки. Такую штуку умеет делать Sparse Table. Только надо учесть: когда мы шагаем вперед на степень двойки надо вычесть из исходной суммы сумму до новой позиции.
Подобные примеры не очень интересны, так как можно использовать бинпоиск. Поэтому добавим еще запрос на изменение элемента в точке. Теперь мы можем использовать только ДО.
Каждая вершина ДО отвечает за отрезок длиной примерно в степень двойки. Соответственно мы можем выбирать, в какого из сыновей мы пойдем дальше. Тоже не забывая поддерживать нашу сумму.