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