Какие функции ложатся в дерево

Дерево отрезков работает не с любой функцией. Требование ровно одно.

Функция должна быть ассоциативной: ответ для объединения двух соседних отрезков должен вычисляться из ответов для них — и только из них.

Формально $f(f(a, b), c) = f(a, f(b, c))$. Сумма, произведение, минимум, максимум, НОД, XOR, побитовые И и ИЛИ — все ассоциативны.

Коммутативность не нужна

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

Единственное следствие: в итеративной реализации придётся накапливать левую и правую части отдельно.

Нейтральный элемент

Запрос иногда попадает в узел, не пересекающийся с отрезком, и должен вернуть значение, не влияющее на ответ: $f(e, x) = f(x, e) = x$.

операция	нейтральный
сумма, XOR	$0$
произведение	$1$
минимум	$+\infty$
максимум	$-\infty$
НОД	$0$, потому что $\gcd(0, x) = x$
побитовое И	все единицы

Строка про НОД смущает больше всего, но она верна: ноль делится на что угодно.

Про бесконечность

Частая ошибка — взять INT_MAX или LLONG_MAX в качестве $+\infty$, а потом что-нибудь к нему прибавить. Переполнение превращает бесконечность в отрицательное число, и минимум становится равен ему.

Берите $10^{18}$: оно заведомо больше любого разумного ответа и переживает сложение с чем угодно разумным.

Идемпотентность и sparse table

Функция идемпотентна, если $f(x, x) = x$. Таковы минимум, максимум, НОД, побитовые И и ИЛИ; сумма и произведение — нет.

Именно это свойство отделяет дерево отрезков от sparse table: та покрывает отрезок двумя перекрывающимися кусками, и перекрытие безвредно только для идемпотентных функций.

Дерево отрезков разбивает отрезок на непересекающиеся узлы, поэтому ему идемпотентность не нужна.

Как проверить свою операцию

Возьмите два соседних отрезка, оставьте от каждого только то, что собираетесь хранить в узле, и спросите себя: достаточно ли этого, чтобы посчитать ответ для склейки?

Если нет — операция не «не ложится в дерево», а просто требует более богатого узла. Об этом — следующая статья.