Изменения

[[Дерево отрезков . Построение|Дерево отрезков]] позволяет осуществлять так называемые '''массовые операцийоперации''', то есть данная структура позволяет выполнять операций операции с несколькими подряд идущими элементами. Причем время работы, как и при других запросах, равно <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>\odot</tex> tree[node].d; tree[node].d = <tex>\perp</tex>; <font color=green> // Нейтральный элемент </font> }

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

Если теперь приходит запрос минимального значения на отрезке, то нам достаточно спуститься по дереву, "протолкнув" все встреченные по пути несогласованности, записанные в вершинах дерева. ==Псевдокод==Используется классическая реализация дерева отрезка с полуинтервалами. Пусть в узлах дерева хранятся структуры из четырех полей:* <tex>left</tex> {{---}} левая граница полуинтервала, за который "отвечает" текущая вершина.* <tex>right</tex> {{---}} правая граница этого полуинтервала.* <tex> min</tex> {{---}} минимум на полуинтервале.* <tex> d</tex> {{---}} несогласованность.  // Процедура "проталкивания" несогласованности детям '''void push(int node) { tree[2 * node + 1].d += tree[node].d; tree[2 * node + 2].d += tree[node].d; tree[node].d = 0; } int get_min''' update(int node, int a, int b, T val) { <font color=green> // node val - текущая вершиназначение, которое поступило в качестве параметра на запрос, a и b - границы запроса</font>

'''if ''' [l, r)<tex>\bigcap cap </tex>[a, b) == <tex> \varnothing</tex> '''return <tex>\infty</tex>'''; '''if ''' [l, r) == <tex>\subset </tex> [a, b) return tree[node].min + tree[node].d; push(node); int m = (l + r) / 2; int ans = min(get_min (node * 2 + 1, a, min(b, m)), get_min (node * 2 + 2, max(a, m), b))); tree[node].min = ans; // Пересчитываем свое значение tree[node].min = min(tree[2 * node + 1].min + tree[2 * node + 1].d, tree[2 * node + 2].min + tree[2 * node + 2].d); } void update(int node, int a, int b, int val) { // val - значение, на которое нужно увеличить отрезок l = tree[node].left; r = tree[node].right; if [l, r)<tex>\bigcap </tex>[a, b) == <tex> \varnothingodot</tex> return; if [l, r) == [a, b) tree[node].d += val; '''return''';

<font color=green>// Вызываем обновление Обновление детей</font>

<font color=green>// Пересчет значения на текущем отрезке </font> tree[node].min ans = min(tree[2 * node + 1].min 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> с текущим ответом истинное значение на отрезке (то есть результат сложения по операции <tex>\odot</tex> значения в вершине с несогласованностью).  '''T''' query(int node, int a, int b) { l = tree[node].left; r = tree[node].right; '''if''' [l, r ) <tex>\cap</tex> [a, b) == <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); T ans = query(node * 2 + 1, a, b) <tex>\oplus</tex> query(node * 2 + 2, a, b)); tree[node].ans = (tree[2 * node + 1].ans <tex>\odot</tex> tree[2 * node + 1].d, ) <tex>\oplus</tex> (tree[2 * node + 2].min + ans <tex>\odot</tex> tree[2 * 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 Дерево отрезков — Википедия]