Теоретическая база

Если вы давно решаете задачи Div1-Div2 на Codeforces, то наверняка уже слышали про сегментное дерево. Звучит возможно для кого-то страшно и не понятно, но на деле это очень полезная структура данных. Проще говоря, сегментное дерево — это такое бинарное дерево, в узлах которого хранятся агрегированные данные о каком-то отрезке массива. За счёт этой древовидной структуры мы можем быстро отвечать на запросы о произвольных сегментах массива да и не только отвечать, но и обновлять элементы.

Представьте, что у нас есть массив, и требуется многократно узнавать что-то про подотрезки этого массива, например, сумму элементов, минимум, максимум, количество каких-то значений и т.д. Сегментное дерево позволяет делать такие запросы очень быстро — обычно за O(log n) на каждый запрос вместо тривиального O(n) перебора. При этом оно достаточно гибкое, поддерживает изменение отдельных элементов, а с дополнительными трюками (ленивые пропагации) может даже массово обновлять целые диапазоны за то же логарифмическое время​. В общем, сегментник может довольно хорошо оптимизировать алгоритм программы, когда обычных массивов и сортировок уже не хватает.

Пример сегментного дерева, построенного для массива arr = {1, 3, 5, 7, 9, 11}. Каждый узел хранит сумму на соответствующем отрезке: корень содержит 36 (сумма на всём отрезке [0;5]), его дети – суммы на [0;2] и [3;5] (9 и 27) и так далее.

Как это работает?

Мы рекурсивно делим массив пополам, пока не дойдём до отдельных элементов. Эти элементы — листья дерева. Затем начинаем “склеивать” информацию снизу вверх: каждый внутренний узел вычисляется из двух дочерних. Например, если нам нужны суммы, то значение узла = сумма левого сына + сумма правого сына. Если нужны минимумы — берём минимум из двух детей, и т.д. В итоге корень хранит агрегат (сумму/мин/макс и пр.) по всему массиву, а путь от корня к листу соответствует делению отрезка на подотрезки.

Когда это нужно?

Сегментное дерево может быть использовано, когда: 1. Нужно эффективно отвечать на запросы о подмножествах элементов массива (сумма на отрезке, максимум на отрезке, НОД на отрезке и т.п.) и при этом между запросами могут происходить изменения отдельных элементов или целых диапазонов, то есть данные динамические. В таком случае простое предвычисление всех ответов не поможет 2. Запросов и обновлений много (десятки и сотни тысяч) и делать их за линейное время слишком медленно

Сегментное дерево обеспечивает (log n) на один запрос или обновление, что обычно укладывается в лимиты при n и количестве запросов порядка 10^5. При этом память сегментника ~4*n элементов для массива размера n — тоже вполне ок.

Примеры задач, решаемых сегментным деревом

Диапазонные суммы, поиск минимума/максимума на отрезке, количество определённых элементов на отрезке, проверка упорядоченности сегмента, даже поиск k-го по счёту элемента. Например, с помощью сегментного дерева можно легко узнать, сколько нулей в заданном диапазоне или найти индекс k-го нуля в массиве​. Кстати, именно такую задачу мы сейчас рассмотрим на практике.

Практическая часть

Давайте на примере рассмотрим задачу 2075F - Beautiful Sequence Returns с недавнего контеста Educational Codeforces Round 176 (Rated for Div. 2), решив её при помощи сегментного дерева и проведём аналогию в сравнении с решением "в лоб".

Рассмотрим решение данной задачи от wishgoodluck — 311252841. Идея данного алгоритма основана на «событийном подходе». Мы предварительно вычисляем два массива (назовём их l и r), которые фиксируют важные границы в исходной последовательности. Эти массивы помогают определить, для каких отрезков происходит «изменение» (увеличение или уменьшение вклада в итоговый ответ). Затем формируется вектор событий — каждый элемент этого вектора задаёт, что на определённом отрезке надо добавить или убрать некоторое значение. В финале итоговая длина искомой последовательности получается как максимальное суммарное изменение.

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

В данном решении сегментное дерево применяется для двух операций:

• Диапазонное обновление (Range Update) Каждое событие из вектора v задаёт, что на отрезке [l,r] нужно прибавить либо +1, либо -1. Сегментное дерево с ленивыми обновлениями позволяет за O(log n) за одно событие обновить сразу весь отрезок, не проходясь по каждому элементу отдельно.
• Запрос максимума (Range Query) После каждого обновления нам нужно быстро узнать, каково максимальное значение на всём диапазоне. Корень дерева (Tree[1].v) всегда хранит максимум среди всех элементов. Это позволяет мгновенно (за O(1) после O(log n) обновлений) узнать текущее оптимальное значение, которое потом используется для вычисления ответа.

Таким образом, сегментное дерево здесь выступает как «агрегатор» всех событий, аккумулируя их влияние на заданных отрезках и позволяя быстро находить максимум.