Изменения

Дерево отрезков позволяет отвечать на запросы к целым отрезкам подряд идущих элементов, причем за то же время <tex>O(\log n)</tex>.

В несогласованном поддереве дерева отрезков в вершинах хранятся не истинные значения сумм (по операции <tex>\oplus</tex>) на отрезках. При этом в корне поддерева, которому соответствует отрезок <tex>a_i..a_j</tex> хранится несогласованность <tex>d</tex>. Если в вершине хранится истинное значение суммы, то <tex>d = \perp</tex> {{---}} нейтральный элемент относительно операции <tex>\odot</tex> (например 0 для прибавления). Для реализации вторая операция должна быть ассоциативной, и должен выполняться распределительный закон с <tex>\oplus</tex>:

Пусть дерево отрезков хранится в массиве <tex>T</tex>. Для реализации массового обновления будем хранить дополнительный массив несогласованностей <tex>d</tex>. Истинные значения <tex>T'[v] = T[v] + d[v]</tex>.

Нумерация массива с нуля, то есть корень дерева {{---}} T[0].

T[v] = min(T[2 * v + 1] + d[2 * v + 1], T[2 * v + 2] + d[2 * v + 2])

}

[[Категория: Дискретная математика и алгоритмы]]

[[Категория: Дерево отрезков]]