Зачем нужно дерево отрезков

Есть массив. Приходят запросы двух видов, вперемешку:

• спросить что-то про отрезок — сумму, минимум, максимум;
• изменить элемент.

Каждый по отдельности решается легко. Вместе — нет.

Что умеют более простые структуры

Префиксные суммы отвечают на запрос суммы за $O(1)$ после $O(n)$ предподсчёта. Но изменение одного элемента портит все префиксы правее него: пересчёт стоит $O(n)$.

Sparse table отвечает за $O(1)$ на минимум и максимум, но перестроить её после изменения стоит $O(n \log n)$.

Обычный массив, наоборот, меняется за $O(1)$, а запрос требует прохода по отрезку — снова $O(n)$.

структура	запрос	изменение
массив	$O(n)$	$O(1)$
префиксные суммы	$O(1)$	$O(n)$
sparse table	$O(1)$	$O(n \log n)$
дерево отрезков	$O(\log n)$	$O(\log n)$

Дерево отрезков не выигрывает ни в одной строке по отдельности. Оно выигрывает, когда обе операции нужны одновременно: $10^5$ запросов вперемешку с $10^5$ изменениями — это $3 \cdot 10^6$ операций вместо $10^{10}$.

Когда дерево не нужно

Если изменений нет вовсе, дерево избыточно. Берите префиксные суммы для сумм и sparse table для минимума с максимумом: они проще и быстрее по константе.

Исключение — память: sparse table занимает $O(n \log n)$, дерево отрезков $O(n)$. При $n = 10^6$ разница между 68 мегабайтами и 8 бывает решающей.

Если, наоборот, нет запросов на отрезке, а только на весь массив, хватит нескольких переменных.

Что дерево умеет сверх этого

Список операций, ради которых его берут даже там, где хватило бы префиксных сумм:

• операция на отрезке: прибавить, присвоить, применить XOR ко всем элементам сразу;
• вопрос «где»: найти $k$-й ноль, первый элемент не меньше $x$ — за один логарифм, а не за два;
• составной ответ: минимум вместе с количеством минимумов, максимальная сумма подотрезка, длина серии.

Каждой из этих возможностей посвящена отдельная статья раздела. Начать стоит с устройства.