0Pricing
Coding Interview Prep · Урок

Дерево отрезков: построение и запросы

Находите минимум, максимум или сумму диапазона за log n

«Дерево отрезков: построение и запросы» — бесплатный урок Coding Interview Prep на CoddyKit. Это урок 3 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Coding Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Coding Interview Prep содержит 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) и разблокировать остальной курс Coding Interview Prep, подпишись на CoddyKit PRO. Курс Coding Interview Prep содержит 4 уроков всего.

Чему я научусь в уроке «Дерево отрезков: построение и запросы»?

Находите минимум, максимум или сумму диапазона за log n Ты практикуешь Coding Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.

Нужен ли мне опыт, чтобы начать Coding Interview Prep?

Предыдущий опыт не требуется. Coding Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 3 из 4.

Сколько времени занимает урок «Дерево отрезков: построение и запросы»?

Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.

Можно ли писать и запускать код в этом уроке Coding Interview Prep?

Да. Каждый урок Coding Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.

Все уроки этого курса

  1. Дерево Фенвика для префиксных сумм
  2. Инверсии с BIT
  3. Дерево отрезков: построение и запросы
  4. Отложенное распространение для обновлений диапазонов
← Назад к Coding Interview Prep