Дерево отрезков: как отвечать на запросы за O(log n)

Дерево отрезков: как отвечать на запросы за O(log n)

Когда-нибудь сталкивались с задачами вида «найди сумму на отрезке [L, R]» для массива из сотен тысяч элементов? Наивный подход — цикл по каждому запросу — даёт O(n) на запрос, что при большом количестве запросов превращается в катастрофу. В этой статье вы узнаете, как дерево отрезков позволяет отвечать на такие запросы за O(log n), и как реализовать его на Python. Это мощный инструмент для собеседований и олимпиадного программирования.

Почему дерево отрезков работает

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

Ключевое свойство: любой запрос [L, R] можно представить как объединение O(log n) непересекающихся узлов дерева. Так как дерево бинарное, количество посещаемых узлов растёт с высотой дерева, а не с длиной диапазона. Мы жертвуем немного памяти (около 4n) ради логарифмического времени ответа на запрос.

Реализация на Python: сумма на отрезке

Начнём с наивного подхода, чтобы понять проблему:

def range_sum(arr, l, r):
    return sum(arr[l:r+1])  # O(r-l+1) → O(n) в худшем случае

Теперь построим дерево отрезков для суммы. Построение занимает O(n), так как каждый узел вычисляется из детей.

class SegTree:
    def __init__(self, data):
        self.n = len(data)
        # размер до следующей степени двойки * 2 (безопасная верхняя граница)
        self.size = 1
        while self.size < self.n:
            self.size <<= 1
        self.tree = [0] * (2 * self.size)

        # загружаем листья
        self.tree[self.size:self.size + self.n] = data

        # строим внутренние узлы
        for i in range(self.size - 1, 0, -1):
            self.tree[i] = self.tree[i << 1] + self.tree[i << 1 | 1]

    # запрос суммы на [l, r] включительно, индексация с нуля
    def query(self, l, r):
        l += self.size
        r += self.size
        res = 0
        while l <= r:
            if l & 1:  # l — правый ребёнок
                res += self.tree[l]
                l += 1
            if not (r & 1):  # r — левый ребёнок
                res += self.tree[r]
                r -= 1
            l >>= 1
            r >>= 1
        return res

    # точечное обновление: устанавливаем arr[pos] = val
    def update(self, pos, val):
        pos += self.size
        self.tree[pos] = val
        pos >>= 1
        while pos:
            self.tree[pos] = self.tree[pos << 1] + self.tree[pos << 1 | 1]
            pos >>= 1

Почему это O(log n)? Цикл query поднимается от листьев к корню, на каждом шаге перемещая l и r на один уровень вверх. Максимальное число итераций — высота дерева, равная ⌈log₂ n⌉. То же самое для update.

Практические задачи

Задача 1: Range Sum Query – Mutable (LeetCode 307)

Поддерживать операции update(i, val) и sumRange(l, r) на массиве. Дерево отрезков решает это за O(log n) на операцию и O(n) на построение.

Задача 2: Range Minimum Query

Если заменить + на min в построении и запросе, получим структуру для поиска минимума на отрезке. Сложность та же, просто другой моноид.

Типичные ошибки

• Ошибка на единицу при смещении листьев: забыли добавить self.size при преобразовании индексов массива в индексы дерева — приводит к чтению/записи не в тот узел.
• Не обновляются предки: после изменения листа обязательно поднимайтесь вверх по дереву. Если пропустить, значения предков останутся устаревшими.

Избегайте этих ошибок — и дерево будет работать как слаженная команда: каждый узел знает, что сообщают его дети, и корень всегда отражает текущее состояние.

Что дальше?

С деревом отрезков в арсенале вы перестанете бояться задач на диапазонные запросы. Вы сможете:

• Обрабатывать сотни тысяч запросов на больших массивах без проблем.
• Расширять идею на другие ассоциативные операции (НОД, побитовое ИЛИ, конкатенация строк), просто меняя функцию объединения.
• Заложить основу для более продвинутых структур: дерево Фенвика, дерево отрезков с ленивыми обновлениями, двумерные деревья отрезков.

Это не только про сдачу тестов, но и про ментальную модель подхода «разделяй и властвуй», который применяется в базах данных, графике, симуляциях и игровых движках.

Практический вывод

Прямо сейчас возьмите задачу, которую вы решали перебором (например, «подсчитать количество чисел больше K на подотрезке»), и попробуйте переформулировать её с помощью дерева отрезков. Если застрянете — пишите в комментариях, обсудим. Откройте для себя силу деревьев отрезков и сделайте ваши запросы молниеносными!