Изменения

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

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

Рассмотрим массовые описанные выше операции на отрезке на примере задачи более подробно. В каждом нижеприведенном псевдокоде в узлах дерева хранятся структуры из четырех полей:* <tex>\mathtt{left}</tex> {{---}} левая граница полуинтервала, за который "Прибавление на отрезкеотвечает"текущая вершина. При этом мы должны отвечать на запрос минимума * <tex>\mathtt{right}</tex> {{---}} правая граница этого полуинтервала.* <tex>\mathtt{ ans}</tex> {{---}} результат на отрезкепо операции <tex>\oplus</tex>.* <tex>\mathtt{ d}</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>O(N)\odot</tex>значенийtree[node].d; tree[node].d = <tex>\perp</tex>; <font color=green> // Нейтральный элемент </font> }

Если теперь приходит запрос минимального значения === update ===Процедура обновления на отрезке. Данная процедура выполняет разбиение текущего отрезка на подотрезки и обновление в них несогласованности. Очень важно выполнить push как только идет рекурсивный вызов от детей, чтобы избежать некорректной обработки в детях. И так как значение в детях могло измениться, то нам достаточно спуститься необходимо выполнить обновление ответа по дереву, "протолкнув" все встреченные по пути несогласованности, записанные в вершинах дереваоперации <tex>\oplus</tex> на текущем отрезке.

'''void''' update(int node, int a, int b, T val) { <font color=green> // val - значение, которое поступило в качестве параметра на запрос, a и b - границы запроса </font> l =Псевдокодtree[node].left; r =tree[node].right; '''if''' [l, r) <tex>\cap </tex> [a, b) == <tex> \varnothing</tex> '''return'''; '''if''' [l, r) <tex>\subset </tex> [a, b) tree[node].d = tree[node].d <tex>\odot</tex> val; '''return'''; push(node); <font color=green>// Обновление детей </font> update(2 * node + 1, a, b, val); update(2 * node + 2, a, b, val); <font color=green>// Пересчет значения на текущем отрезке </font> tree[node].ans = (tree[2 * node + 1].ans <tex>\odot</tex> tree[2 * node + 1].d) <tex>\oplus</tex> (tree[2 * node + 2].ans <tex>\odot</tex> tree[2 * node + 2].d); }

Нумерация массива === query ===Получение ответа по операции <tex>\oplus</tex>. Отличие от операции обновления лишь в том, что для каждого отрезка разбиения необходимо не обновить несогласованность, а сложить по операции <tex>\oplus</tex> с нуля, текущим ответом истинное значение на отрезке (то есть корень дерева {{---}} T[0]результат сложения по операции <tex>\odot</tex> значения в вершине с несогласованностью).

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