Дерево отрезков: запросы и обновления за O(log n)

Структура, которая отвечает на запрос «сумма/минимум на отрезке» и меняет элементы — обе операции за O(log n).

Дерево отрезков — структура данных над массивом, позволяющая за O(log n) выполнять запросы на отрезке (сумма, минимум, максимум) и точечно обновлять элементы.

Зачем это нужно

Помнишь префиксные суммы из раздела 2? Они отвечают на запрос суммы за O(1), но ломаются при обновлениях: изменив один элемент, придётся пересчитать весь префиксный массив за O(n). Когда обновления и запросы идут вперемешку (а это очень частый сценарий), нужна структура, у которой обе операции дёшевы. Дерево отрезков даёт ровно это: и запрос, и обновление за O(log n). Это базовая структура уровня USACO Gold и обязательный инструмент для задач с динамическими запросами на отрезках.

Идея «на пальцах»

Разобьём массив пополам, каждую половину снова пополам, и так до отдельных элементов — получится двоичное дерево. В каждом узле храним агрегат своего отрезка (например, сумму). Тогда:

Запрос суммы на [l, r] собирается из O(log n) уже посчитанных узлов — не нужно складывать поэлементно.
Обновление одного элемента меняет агрегаты только на пути от листа к корню — это высота дерева, O(log n).

Высота дерева — log n, поэтому и запрос, и обновление «касаются» лишь O(log n) узлов.

Итеративная реализация на массиве

Есть рекурсивная версия (нагляднее) и итеративная на массиве размера 2n (короче и быстрее, особенно в Python). Разберём итеративную для суммы. Листья кладём в ячейки [n, 2n), внутренние узлы — в [1, n), где у узла i дети 2i и 2i+1.

class SegTree:
    def __init__(self, data):
        self.n = len(data)
        self.t = [0] * (2 * self.n)
        # листья
        for i in range(self.n):
            self.t[self.n + i] = data[i]
        # внутренние узлы — снизу вверх
        for i in range(self.n - 1, 0, -1):
            self.t[i] = self.t[2 * i] + self.t[2 * i + 1]

    def update(self, pos, val):
        i = pos + self.n
        self.t[i] = val               # меняем лист
        i //= 2
        while i >= 1:                 # обновляем предков до корня
            self.t[i] = self.t[2 * i] + self.t[2 * i + 1]
            i //= 2

    def query(self, l, r):            # сумма на полуинтервале [l, r)
        res = 0
        l += self.n; r += self.n
        while l < r:
            if l & 1:                 # l — правый ребёнок: берём и сдвигаем
                res += self.t[l]; l += 1
            if r & 1:                 # r — правый ребёнок: берём левого соседа
                r -= 1; res += self.t[r]
            l //= 2; r //= 2
        return res

st = SegTree([1, 3, 5, 7, 9, 11])
print("Сумма [1,5):", st.query(1, 5))        # 3+5+7+9
st.update(2, 100)                            # a[2]: 5 -> 100
print("После update a[2]=100, сумма [1,5):", st.query(1, 5))

Разберём query(1, 5) — это сумма элементов с индексами 1,2,3,4: 3+5+7+9 = 24. После update(2, 100) элемент с индексом 2 стал 100, поэтому сумма того же отрезка — 3+100+7+9 = 119. Заметь: мы не пересчитывали весь массив, обновление прошло по log n узлам.

Вывод:

Сумма [1,5): 24
После update a[2]=100, сумма [1,5): 119

Минимум вместо суммы

Дерево отрезков работает с любой ассоциативной операцией. Чтобы получить минимум на отрезке, достаточно заменить + на min, а нейтральный элемент 0 — на «бесконечность».

INF = float("inf")
a = [5, 2, 8, 1, 9, 3]
n = len(a)
t = [INF] * (2 * n)
for i in range(n):
    t[n + i] = a[i]
for i in range(n - 1, 0, -1):
    t[i] = min(t[2 * i], t[2 * i + 1])

def query_min(l, r):               # минимум на [l, r)
    res = INF
    l += n; r += n
    while l < r:
        if l & 1: res = min(res, t[l]); l += 1
        if r & 1: r -= 1; res = min(res, t[r])
        l //= 2; r //= 2
    return res

print("min [0,6):", query_min(0, 6))
print("min [2,5):", query_min(2, 5))

Это иллюстрирует общность структуры: меняется только операция и нейтральный элемент, скелет тот же. Так получают деревья для суммы, минимума, максимума, НОД и многого другого.

Вывод:

min [0,6): 1
min [2,5): 1

Сложность

Операция	Время
Построение	`O(n)`
Запрос на отрезке	`O(log n)`
Точечное обновление	`O(log n)`
Память	`O(n)`

Для сравнения: если бы и запросы, и обновления делать наивно, любое из них стоило бы O(n). Дерево отрезков балансирует обе операции на O(log n) — отсюда его ценность.

Подводные камни и развитие

Полуинтервалы. В итеративной версии запрос — на [l, r) (правый конец не включён); легко ошибиться на единицу.
Дерево Фенвика. Для одной только суммы есть более простая и компактная структура — дерево Фенвика (BIT), тоже O(log n); её часто предпочитают, когда хватает суммы.
Обновление на отрезке. Чтобы прибавлять на целом отрезке за O(log n), нужна отложенная протяжка (lazy propagation) — следующий уровень той же идеи.
Python и константа. Дерево отрезков в Python с большой константой может быть на грани TLE; итеративная версия и аккуратный код важны.

Итог

Дерево отрезков даёт запрос на отрезке и точечное обновление — обе операции за O(log n).
Работает с любой ассоциативной операцией: сумма, минимум, максимум, НОД — меняется лишь операция и нейтральный элемент.
Нужно, когда обновления и запросы перемешаны (где префиксные суммы бессильны).
Развитие: дерево Фенвика (проще для суммы) и lazy propagation (обновление на отрезке).