Изменения

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

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

Пусть дерево отрезков храниться в массиве Для эффективной реализации будем использовать описанную выше структуру {{---}} несогласованные поддеревья. В каждой вершине, помимо непосредственно результата выполнения операции <tex>\oplus</tex>, храним несогласованность {{---}} величина, с которой нужно выполнить операцию <tex>T\odot</tex>для всех элементов текущего отрезка. Для реализации Тем самым мы сможем обрабатывать запрос массового обновления будем хранить дополнительный массив несогласованностей на любом подотрезке эффективно, вместо того чтобы изменять все <tex>dO(N)</tex>значений. Истинные значения Как известно из определения несогласованных поддеревьев, в текущий момент времени не в каждой вершине дерева хранится истинное значение, однако когда мы обращаемся к текущему элементу мы работаем с верными данными. Это обеспечивается "проталкиванием" несогласованности детям (процедура push) при каждом обращений к текущей вершине. При этом после обращения к вершине необходимо пересчитать значение по операции <tex>T'[v] = T[v] + d[v]\oplus</tex>, так как значение в детях могло измениться.

Псевдокод (нумерация массивов с нуля, то есть корень Рассмотрим описанные выше операции более подробно. В каждом нижеприведенном псевдокоде в узлах дерева хранятся структуры из четырех полей:* <tex>\mathtt{left}</tex> {{---}} T[0]):левая граница полуинтервала, за который "отвечает" текущая вершина. get_min(v, l, r) * <tex>\mathtt{right}</tex> {{---}} правая граница этого полуинтервала. * <tex>\mathtt{ ans}</tex> {{---}} результат на отрезке по операции <tex>\oplus</tex>.* <tex>\mathtt{ d}</ v tex> {{-- текущая вершина-}} несогласованность. === push ==="Проталкивание" несогласованности детям. Необходимо выполнять как только идет рекурсивный запуск от текущей вершины к её детям. Нужно это для того, l и r - границы запросачтобы в детях в момент обработки были корректные данные. if '''void''' push(отрезок соответственный v не пересекается с [l, r]int node) return inf { <font color=green>// бесконечность node - нейтральный элемент относительно minтекущая вершина </font> if (отрезок соответственный v содержится в [l, r]) 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;