Дерево отрезков: построение и запросы
Находите минимум, максимум или сумму диапазона за log n
«Дерево отрезков: построение и запросы» — бесплатный урок Competitive Programming Academy на CoddyKit. Это урок 3 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Competitive Programming Academy, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Competitive Programming Academy содержит 4 уроков всего.
За пределами дерева Фенвика
Дерево Фенвика отлично подходит для сумм, но дерево отрезков умеет работать с минимумом, максимумом, НОД и другими операциями. Это универсальный инструмент для запросов по диапазонам.
Дерево над диапазонами
Каждая вершина отвечает за диапазон массива. Корень охватывает весь массив, а дочерние вершины делят его пополам, пока в листьях не останутся отдельные элементы.
Хранение в массиве
Мы храним дерево в плоском массиве размера 2n или 4n. Вершина 1 — корень, а потомки вершины i находятся в позициях 2i и 2i+1.
seg = [0] * (2 * n)Листья хранят данные
В итеративной форме исходные значения находятся во второй половине массива, в индексах от n до 2n-1.
for i in range(n):
seg[n + i] = a[i]Построение снизу вверх
Каждая внутренняя вершина получается с помощью операции combine над двумя её потомками. Заполните вершины от n-1 до 1, и всё дерево будет готово.
for i in range(n - 1, 0, -1):
seg[i] = seg[2*i] + seg[2*i+1]Операция combine
Функция combine определяет поведение дерева. Используйте сложение для сумм, минимум для поиска минимума или максимум для поиска максимума. Замените её, чтобы изменить запрос.
def combine(x, y):
return min(x, y)Точечное обновление, затем подъём
Чтобы изменить одно значение, установите его в листе и поднимайтесь к корню, пересчитывая по пути каждого родителя на основе двух его потомков.
i += n
seg[i] = value
while i > 1:
i //= 2
seg[i] = combine(seg[2*i], seg[2*i+1])Запрос полуоткрытого диапазона
Запросы по диапазону просматривают его с обоих концов, добавляя пограничные вершины к ответу. Интервал является полуоткрытым: включает l, но не включает r.
Итеративный цикл запроса
Перемещайте l и r навстречу друг другу. Если индекс находится на нечётной границе, включите соответствующую вершину в ответ, прежде чем перемещать указатель.
while l < r:
if l & 1: res = combine(res, seg[l]); l += 1
if r & 1: r -= 1; res = combine(res, seg[r])
l //= 2; r //= 2Логарифмическое время с обоих концов
Построение занимает O(n), а каждое обновление и запрос — O(log n). Именно такой баланс делает деревья отрезков настолько универсальными.
Помните о нейтральном элементе
Начинайте результат с нейтрального элемента операции: с 0 для суммы, с бесконечности для минимума и с отрицательной бесконечности для максимума. Неправильное начальное значение даёт неправильные ответы.
res = float('inf')Быстрая проверка
Где находятся исходные данные в итеративном дереве?
Повторение: гибкие диапазоны
Вы построили дерево отрезков: листья находятся во второй половине массива, родители получают значения через combine, а обновления и запросы суммы, минимума или максимума выполняются за O(log n). 🌳
Часто задаваемые вопросы
Урок «Дерево отрезков: построение и запросы» бесплатный?
Да — полный текст урока «Дерево отрезков: построение и запросы» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Competitive Programming Academy, подпишись на CoddyKit PRO. Курс Competitive Programming Academy содержит 4 уроков всего.
Чему я научусь в уроке «Дерево отрезков: построение и запросы»?
Находите минимум, максимум или сумму диапазона за log n Ты практикуешь Competitive Programming Academy с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Competitive Programming Academy?
Предыдущий опыт не требуется. Competitive Programming Academy на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 3 из 4.
Сколько времени занимает урок «Дерево отрезков: построение и запросы»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Competitive Programming Academy?
Да. Каждый урок Competitive Programming Academy включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Дерево Фенвика для префиксных сумм
- Инверсии с BIT
- Дерево отрезков: построение и запросы
- Отложенное распространение для обновлений диапазонов