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

Представьте: нужно много раз вычислять сумму на отрезке массива, а потом ещё и обновлять элементы. Если считать в лоб — for i in range(l, r+1): total += arr[i] — то на 10⁵ запросах программа зависнет. Что делать? Дерево отрезков (сегментное дерево) превращает O(n·q) в O((n+q)·log n). Разберёмся, как это работает.

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

Допустим, у нас есть массив, и мы хотим знать сумму любого отрезка [l, r]. Если разбить отрезок на несколько заранее вычисленных кусков, то нужно сложить только их значения, а не каждый элемент. Дерево отрезков — это бинарное дерево, где каждый узел хранит агрегат (сумму, минимум, максимум и т.д.) для своего отрезка. Корень покрывает весь массив [0, n-1], его дети — левую и правую половины, и так до листьев, которые соответствуют отдельным элементам.

Два ключевых факта:

• Значение узла = сумма значений его детей. Это позволяет построить дерево снизу вверх за O(n).
• Любой отрезок можно представить как O(log n) непересекающихся узлов. При запросе мы либо берём целый узел (если его отрезок полностью внутри запроса), либо спускаемся дальше. Высота дерева — log₂n, поэтому мы посетим не более 2·log₂n узлов.

Итог: построение — O(n), запрос — O(log n), обновление — O(log n).

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

Вот итеративная версия (без рекурсии) — её удобно использовать на собеседованиях.

class SegTree:
    def __init__(self, data):
        """
        Построение дерева за O(n).
        """
        self.n = len(data)
        # size — ближайшая степень двойки >= n
        self.size = 1
        while self.size < self.n:
            self.size <<= 1
        # массив дерева: листья начинаются с индекса size
        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]

    def _apply(self, pos, value):
        """
        Устанавливает лист pos в value и обновляет предков.
        """
        idx = pos + self.size
        self.tree[idx] = value
        idx >>= 1
        while idx:
            self.tree[idx] = self.tree[idx << 1] + self.tree[idx << 1 | 1]
            idx >>= 1

    def update(self, idx, value):
        """
        Точечное обновление: arr[idx] = value (O(log n)).
        """
        self._apply(idx, value)

    def query(self, l, r):
        """
        Сумма на отрезке [l, r] включительно (O(log n)).
        """
        l += self.size
        r += self.size + 1  # делаем r исключительным
        res = 0
        while l < r:
            if l & 1:
                res += self.tree[l]
                l += 1
            if r & 1:
                r -= 1
                res += self.tree[r]
            l >>= 1
            r >>= 1
        return res

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

• Листья (size … size+n-1) хранят исходный массив.
• Каждый внутренний узел хранит сумму детей. После построения инвариант выполняется.
• update меняет лист и поднимается вверх, пересчитывая предков.
• query поднимает два указателя l и r, добавляя целые узлы, когда указатель — правый ребёнок (значит, его отрезок полностью внутри запроса). Из-за подъёма на один уровень за итерацию мы касаемся O(log n) узлов.

Частые ошибки

Где пригодится на собеседованиях

Дерево отрезков — стандартный инструмент для задач вида «запрос на отрезке + точечное обновление». Вот две классические задачи FAANG:

• Range Sum Query with Updates (LeetCode 307) — наша реализация решает её за O((n+q)·log n).
• Maximum Subarray Sum in a Range — нужно хранить в узле четыре значения: сумму, максимальный префикс, максимальный суффикс и максимальную подсумму. Логика слияния та же, запрос возвращает максимальную подсумму на отрезке.

Имея шаблон дерева отрезков под рукой, вы чувствуете себя увереннее на собеседовании.

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

Прямо сейчас возьмите лист бумаги или IDE и реализуйте дерево отрезков для поиска минимума на отрезке (range minimum query) с точечными обновлениями. Протестируйте на случайном массиве, сравните скорость с наивным O(n) подходом. Когда увидите ускорение в log раз, вы поймёте, что прокачались.