Изменения

[[Дерево отрезков . Построение|Дерево отрезков]] позволяет осуществлять так называемые '''массовые операцийоперации''', то есть данная структура позволяет выполнять операций операции с несколькими подряд идущими элементами. Причем время работы, как и при других запросах, равно <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 ===Процедура обновления на отрезке. Данная процедура выполняет разбиение текущего отрезка на подотрезки и обновление в узлах дерева хранятся структуры из четырех полей:* <tex>left</tex> {{---}} левая граница полуинтерваланих несогласованности. Очень важно выполнить push как только идет рекурсивный вызов от детей, за который "отвечает" текущая вершиначтобы избежать некорректной обработки в детях.* И так как значение в детях могло измениться, то необходимо выполнить обновление ответа по операции <tex>right\oplus</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 - границы запроса l = tree[node].left; r = tree[node].right; if [l, r)<tex>\bigcap </texfont>[a, b) == <tex> \varnothing</tex> return <tex>\infty</tex>; if [l, r) == [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 = min(tree[2 * node + 1].min + tree[2 * node + 1].d, tree[2 * node + 2].min + tree[2 * node + 2].d); return ans; } void update(int node, int a, int b, int val) { // val - значение, на которое нужно увеличить отрезок

'''if ''' [l, r)<tex>\bigcap 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''';

<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].min + ans <tex>\odot</tex> tree[2 * node + 2].d);

==Псевдокод в общем виде= query ===Пусть поступают запросы двух типов {{---}} поиск элемента, соответствующего операций Получение ответа по операции <tex>\oplus</tex>. Отличие от операции обновления лишь в том, что для каждого отрезка разбиения необходимо не обновить несогласованность, и массовое обновление на отрезке относительно операций а сложить по операции <tex>\odotoplus</tex>. Используется классическая реализация дерева отрезка с полуинтервалами. Пусть в узлах дерева хранятся структуры из четырех полей:* <tex>left</tex> {{---}} левая граница полуинтервала, за который "отвечает" текущая вершина.* <tex>right</tex> {{---}} правая граница этого полуинтервала.* <tex> ans</tex> {{---}} сумма текущим ответом истинное значение на отрезке (то есть результат сложения по операций операции <tex>\oplusodot</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; } // Процедура ответа на множественные запросы. void update'''T''' query(int node, int a, int b, int val) { // val - значение, на которое нужно увеличить отрезок

'''if ''' [l, r)<tex>\bigcap cap</tex>[a, b) == <tex> \varnothing</tex> '''return; if [l, r) == [a, b) tree[node].d += val; return; push(node); ''' <tex>\perp<// Вызываем обновление детей update(2 * node + 1, a, b, val); update(2 * node + 2, a, b, val); tree[node].min = min(tree[2 * node + 1].min + tree[2 * node + 1].d, tree[2 * node + 2].min + tree[2 * node + 2].d); } // Функция ответа на запросы int get(int node, int a, int b) { // node - текущая вершина, a и b - границы запроса l = tree[node].left; r = tree[node].righttex>; '''if ''' [l, r)<tex>\bigcap subset</tex>[a, b) == <tex> \varnothing</tex> '''return ''' tree[node].ans <tex>\inftyodot</tex>; if [l, r) == [a, b) return tree[node].min + tree[node].d;

int m = (l + r) / 2; int T ans = min(get_min query(node * 2 + 1, a, min(b, m)), <tex>\oplus</tex> get_min query(node * 2 + 2, max(a, m), b))); // Пересчитываем свое значение 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].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 Дерево отрезков — Википедия]