Изменения

[[Дерево отрезков . Построение|Дерево отрезков]] позволяет отвечать на запросы к целым отрезкам подряд идущих элементовосуществлять '''массовые операции''', причем за то же есть данная структура позволяет выполнять операции с несколькими подряд идущими элементами. Причем время работы, как и при других запросах, равно <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>\oplusodot</tex>должна быть ассоциативной, и операции должны удовлетворять свойству дистрибутивности:

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

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

Пусть дерево отрезков хранится Рассмотрим описанные выше операции более подробно. В каждом нижеприведенном псевдокоде в массиве узлах дерева хранятся структуры из четырех полей:* <tex>T\mathtt{left}</tex>{{---}} левая граница полуинтервала, за который "отвечает" текущая вершина. Для реализации массового обновления будем хранить дополнительный массив несогласованностей * <tex>d\mathtt{right}</tex> {{---}} правая граница этого полуинтервала.* <tex>\mathtt{ ans}</tex> {{---}} результат на отрезке по операции <tex>\oplus</tex>. Истинные значения * <tex>T'[v] = T[v] + \mathtt{ d[v]}</tex>{{---}} несогласованность.

==Псевдокод=push ==="Проталкивание" несогласованности детям. Необходимо выполнять как только идет рекурсивный запуск от текущей вершины к её детям. Нужно это для того, чтобы в детях в момент обработки были корректные данные. '''void''' push(int node) { <font color=green>// node - текущая вершина </font> tree[2 * node + 1].d = tree[2 * node + 1].d <tex>\odot</tex> tree[node].d; tree[2 * node + 2].d = tree[2 * node + 2].d <tex>\odot</tex> tree[node].d; tree[node].d = <tex>\perp</tex>; <font color=green> // Нейтральный элемент </font> }

Нумерация массива с нуля=== update ===Процедура обновления на отрезке. Данная процедура выполняет разбиение текущего отрезка на подотрезки и обновление в них несогласованности. Очень важно выполнить push как только идет рекурсивный вызов от детей, чтобы избежать некорректной обработки в детях. И так как значение в детях могло измениться, то есть корень дерева {{---}} T[0]необходимо выполнить обновление ответа по операции <tex>\oplus</tex> на текущем отрезке.

get_min'''void''' update(vint node, lint a, int b, rT val) { <font color=green> // v val - текущая вершиназначение, l которое поступило в качестве параметра на запрос, a и r b - границы запроса</font> l = tree[node].left; r = tree[node].right; '''if (отрезок соответствующий v не пересекается с ''' [l, r])<tex>\cap </tex> [a, b) == <tex> \varnothing</tex> '''return inf // бесконечность - нейтральный элемент относительно min'''; '''if (отрезок соответствующий v содержится в ''' [l, r]) <tex>\subset </tex> [a, b) return tree[vnode] + .d= tree[vnode].d <tex>\odot</tex> val; // Раздаем детям '''return'''; d[2 * v + 1] = d[2 * v + 1] + d[v] d[2 * v + 2] = d[2 * v + 2] + d[v] push(node); d[v] <font color= 0 green>// Вызываем функцию от Обновление детей</font> ans = min(get_min update(2 * v node + 1, la, b, rval), get_min; update(2 * v node + 2, la, b, r)val); <font color=green>// Пересчитываем свое значениеПересчет значения на текущем отрезке </font> T tree[vnode] .ans = min(Ttree[2 * v node + 1] + d.ans <tex>\odot</tex> tree[2 * v node + 1], T.d) <tex>\oplus</tex> (tree[2 * v node + 2] + d.ans <tex>\odot</tex> tree[2 * v node + 2].d) return ans;

=== query ===Получение ответа по операции <tex>\oplus</tex>. Отличие от операции обновления лишь в том, что для каждого отрезка разбиения необходимо не обновить несогласованность, а сложить по операции <tex>\oplus</tex> с текущим ответом истинное значение на отрезке (то есть результат сложения по операции <tex>\odot</tex> значения в вершине с несогласованностью).  update'''T''' query(vint node, l, rint a, xint b) { // x - сколько нужно прибавить на отрезке l = tree[node].left; r = tree[node].right; '''if (отрезок соответственный v не пересекается с ''' [l, r])<tex>\cap</tex> [a, b) == <tex> \varnothing</tex> '''return''' <tex>\perp</tex>; '''if (отрезок соответственный v содержится в ''' [l, r]) { d<tex>\subset</tex> [v] = d[v] + xa, b) '''return } // Раздаем детям d''' tree[2 * v + 1node] = d.ans <tex>\odot</tex> tree[2 * v + 1node] + .d[v]; d[2 * v + 2] = d[2 * v + 2] + d[v] push(node); d[v] T ans = 0 // Вызываем функцию от детей updatequery(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 * v node + 1] + d.ans <tex>\odot</tex> tree[2 * v node + 1], T.d) <tex>\oplus</tex> (tree[2 * v node + 2] + d.ans <tex>\odot</tex> tree[2 * v node + 2].d); '''return''' ans;

==СсылкиСм. также==*[[Дерево отрезков. Построение]] * [[Реализация запроса в дереве отрезков сверху]] *[[Реализация запроса в дереве отрезков снизу]] ==Источники информации== * [http://e-maxx.ru/algo/segment_tree MAXimal :: algo :: Дерево отрезков] * [http://ru.wikipedia.org/wiki/%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%BE%D1%82%D1%80%D0%B5%D0%B7%D0%BA%D0%BE%D0%B2 Дерево отрезков — Википедия]