Изменения

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

Массовые Пусть дерево отрезков хранит в вершинах результат выполнения операции <tex>\oplus</tex> на текущем отрезке рассмотрим на примере минимума на отрезке и прибавления на отрезке, а запрос обновления идет по операции <tex>\odot</tex>.

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

Псевдокод #<tex>a \odot (нумерация массивов с нуля, то есть корень дерева - T[0]b \odot c) = (a \odot b):\odot c</tex> get_min#<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 - сколько нужно прибавить на отрезкеfont> if update(отрезок соответственный v не пересекается с [l2 * node + 1, a, b, r]val); return if update(отрезок соответственный v содержится в [l2 * node + 2, a, b, r]val) {; <font color=green>// Пересчет значения на текущем отрезке </font> d tree[vnode] .ans = d[v] + x return } d(tree[2*vnode +1] = d.ans <tex>\odot</tex> tree[2*vnode +1] + .d[v]) <tex>\oplus</tex> d (tree[2*vnode +2] = d.ans <tex>\odot</tex> tree[2*vnode +2] + .d); } === query ===Получение ответа по операции <tex>\oplus</tex>. Отличие от операции обновления лишь в том, что для каждого отрезка разбиения необходимо не обновить несогласованность, а сложить по операции <tex>\oplus</tex> с текущим ответом истинное значение на отрезке (то есть результат сложения по операции <tex>\odot</tex> значения в вершине с несогласованностью).  '''T''' query(int node, int a, int b) { l = tree[vnode].left; d r = tree[vnode] .right; '''if''' [l, r ) <tex>\cap</tex> [a, b) == 0<tex> \varnothing</tex> '''return''' <tex>\perp</tex>; '''if''' [l, r) <tex>\subset</tex> [a, b) '''return''' tree[node].ans <tex>\odot</tex> tree[node].d; push(node); update T ans = query(node * 2*v+1, la, r, xb)<tex>\oplus</tex> update query(node * 2*v+2, la, r, xb)); T 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;