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

Если вы давно решаете задачи 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-го нуля в массиве​. Кстати, именно такую задачу мы сейчас рассмотрим на практике.