Изменения

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

Массовые операции на отрезке ==Несогласованные поддеревья==Сперва рассмотрим на примере минимума на отрезке и прибавления на отрезкетак называемые '''несогласованные поддеревья'''.

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

Псевдокод В несогласованном поддереве дерева отрезков в вершинах хранятся не истинные значения сумм (нумерация массивов с нуляпо операции <tex>\oplus</tex>) на отрезках, однако гарантируется, что на запрос они отвечают верно. При этом в корне поддерева, которому соответствует отрезок <tex>a_i..a_j</tex> хранится несогласованность <tex>d</tex>. Если в вершине хранится истинное значение суммы, то есть корень дерева <tex>d = \perp</tex> {{--- T[}} нейтральный элемент относительно операции <tex>\odot</tex> (например 0]для прибавления). Для реализации операция <tex>\odot</tex> должна быть ассоциативной, и операции должны удовлетворять свойству дистрибутивности: get_min#<tex>a \odot (b \odot c) = (a \odot b) \odot c</tex>#<tex>(a \oplus b) \odot c = (a \odot c) \oplus (v, l, rb \odot c) {</tex> ==Массовое обновление==  Рассмотрим в общем виде реализацию массовой операции на отрезке. Пусть необходимо отвечать на запросы относительно операции <tex>\oplus</tex>, а запрос массового обновления идет по операции <tex>\odot</ v tex>. Для эффективной реализации будем использовать описанную выше структуру {{- текущая вершина--}} несогласованные поддеревья. В каждой вершине, помимо непосредственно результата выполнения операции <tex>\oplus</tex>, l и r храним несогласованность {{--- границы запроса if }} величина, с которой нужно выполнить операцию <tex>\odot</tex> для всех элементов текущего отрезка. Тем самым мы сможем обрабатывать запрос массового обновления на любом подотрезке эффективно, вместо того чтобы изменять все <tex>O(отрезок соответственный v N)</tex> значений. Как известно из определения несогласованных поддеревьев, в текущий момент времени не пересекается в каждой вершине дерева хранится истинное значение, однако когда мы обращаемся к текущему элементу мы работаем с [lверными данными. Это обеспечивается "проталкиванием" несогласованности детям (процедура push) при каждом обращений к текущей вершине. При этом после обращения к вершине необходимо пересчитать значение по операции <tex>\oplus</tex>, так как значение в детях могло измениться. Рассмотрим описанные выше операции более подробно. В каждом нижеприведенном псевдокоде в узлах дерева хранятся структуры из четырех полей:* <tex>\mathtt{left}</tex> {{---}} левая граница полуинтервала, r])за который "отвечает" текущая вершина.* <tex>\mathtt{right}</tex> {{---}} правая граница этого полуинтервала. return inf * <tex>\mathtt{ ans}</tex> {{---}} результат на отрезке по операции <tex>\oplus</tex>.* <tex>\mathtt{ d}</ бесконечность tex> {{-- нейтральный элемент относительно min-}} несогласованность. === push ==="Проталкивание" несогласованности детям. Необходимо выполнять как только идет рекурсивный запуск от текущей вершины к её детям. Нужно это для того, чтобы в детях в момент обработки были корректные данные. if '''void''' push(отрезок соответственный v содержится в [l, r]int node){ <font color=green>// node - текущая вершина </font> return tree[v] + d[v] d[2*vnode +1] .d = dtree[2*vnode +1] + .d<tex>\odot</tex> tree[vnode].d; d tree[2*vnode +2] .d = dtree[2*vnode +2] + .d<tex>\odot</tex> tree[vnode].d; d tree[vnode] .d = 0 ans <tex>\perp</tex>; <font color= min(get_min(2*v+1, l, r), get_min(2*v+2, l, r)) T[v] = min(T[2*v+1] + d[2*v+1], T[2*v+2] + d[2*v+2]) return ansgreen> // Нейтральный элемент </font>

update push(v, l, r, xnode) {; <font color=green>// x - сколько нужно прибавить на отрезке if (отрезок соответственный v не пересекается с [l, r]) return if (отрезок соответственный v содержится в [l, r]) { d[v] = d[v] + x return } d[2*v+1] = d[2*v+1] + d[v]Обновление детей </font> d[2*v+2] = d[2*v+2] + d[v] d[v] = 0 update(2*vnode +1, la, rb, xval); update(2*vnode +2, la, rb, xval); T<font color=green>// Пересчет значения на текущем отрезке </font> tree[vnode] .ans = min(Ttree[2*vnode +1]+d.ans <tex>\odot</tex> tree[2*vnode +1],T.d) <tex>\oplus</tex> (tree[2*vnode +2]+d.ans <tex>\odot</tex> tree[2*vnode +2].d) return ans;