Корневая или дерево отрезков

Корневая декомпозиция и дерево отрезков решают пересекающиеся, но разные множества задач. Выбирать между ними стоит осознанно, а не по привычке.

Таблица выбора

задача	чем решать
сумма или максимум на отрезке, точечные изменения	дерево отрезков
прибавление на отрезке, сумма на отрезке	дерево отрезков с отложенными метками
странная сводка, которую тяжело слить из двух половин	корневая
вставки и удаления в середину	корневая с перестроением
прыжки вперёд с изменениями	прыжки по блокам
количество различных на отрезке, запросы офлайн	алгоритм Мо
$k$-я порядковая статистика на отрезке	дерево Меркла или Мо, но не простая корневая

Чем корневая хуже

Асимптотика. $\sqrt{n}$ против $\log n$ - при $n = 10^5$ это 316 против 17, разница почти в двадцать раз. На больших $n$ корневая просто не пройдёт.

Константа при этом маленькая. Внутренний цикл корневой - линейный проход по подряд идущей памяти, и процессор его любит. Поэтому на $n$ до $10^5$ разница на практике меньше, чем следует из формул: у дерева отрезков переходы по указателям и плохая локальность.

Чем корневая лучше

Пишется за десять минут и почти не ошибается. Нет рекурсии, нет проталкивания меток вниз, нет вопроса «какой отрезок отвечает этой вершине».

Не требует ассоциативности. Дерево отрезков сливает два ответа в один и потому требует, чтобы операция была ассоциативной. Корневая может пересчитать блок целиком - а для этого достаточно уметь считать ответ за $O(B)$ хоть как.

Позволяет менять количество элементов. Вставки и удаления в середину для обычного дерева отрезков недоступны.

Даёт офлайновый алгоритм Мо, у которого прямого аналога на дереве отрезков нет.

Практическое правило

Если задача - классическая сумма или максимум с обновлениями, берите дерево отрезков: оно быстрее и его всё равно надо уметь.

Если сводка странная, набор элементов меняется, или просто хочется дописать решение за десять минут и уложиться в лимит - берите корневую. На олимпиадных размерах она проходит гораздо чаще, чем кажется по асимптотике.

И проверяйте бюджет заранее: $q\sqrt{n}$ при $q = n = 10^5$ - это $3 \cdot 10^7$ операций, что укладывается в секунду с запасом. При $n = 10^6$ уже $10^9$, и корневая не годится.