Изменения

Перейти к: навигация, поиск
Нет описания правки
Дерево отрезков позволяет отвечать на запросы к целым отрезкам подряд идущих элементовосуществлять так называемые '''массовые операций''', причем за то же есть данная структура позволяет выполнять операций с несколькими подряд идущими элементами. Причем время работы, как и при других запросах, равно <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>a \odot (b \odot c) = (a \odot b) \odot c</tex>
Анонимный участник

Навигация