Изменения

[[Дерево отрезков . Построение|Дерево отрезков]] позволяет отвечать на запросы к целым отрезкам подряд идущих элементовосуществлять '''массовые операции''', причем за то же есть данная структура позволяет выполнять операции с несколькими подряд идущими элементами. Причем время работы, как и при других запросах, равно <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>O(N)</tex> значений. Как известно из определения несогласованных поддеревьев, в текущий момент времени не в каждой вершине дерева хранится истинное значение, однако когда мы обращаемся к текущему элементу мы работаем с верными данными. Это обеспечивается "Прибавление на отрезкепроталкиванием"несогласованности детям (процедура push) при каждом обращений к текущей вершине. При этом мы должны отвечать на запрос минимума на отрезкепосле обращения к вершине необходимо пересчитать значение по операции <tex>\oplus</tex>, так как значение в детях могло измениться.

Для эффективной реализаций будем использовать описанную Рассмотрим описанные выше структуру операции более подробно. В каждом нижеприведенном псевдокоде в узлах дерева хранятся структуры из четырех полей:* <tex>\mathtt{left}</tex> {{---}} несогласованные поддеревьялевая граница полуинтервала, за который "отвечает" текущая вершина. В каждой вершине, помимо непосредственно суммы, храним несогласованность * <tex>\mathtt{right}</tex> {{---}} сколько необходимо прибавить ко всем числам правая граница этого отрезка(соответственно при запросе минимума истинный минимум на отрезке при корректной несогласованности полуинтервала.* <tex>\mathtt{ ans}</tex> {{---}} сумма несогласованности и значения в вершине)результат на отрезке по операции <tex>\oplus</tex>. Тем самым мы сможем обрабатывать запрос прибавления на любом подотрезке эффективно, вместо того чтобы изменять все * <tex>O(N)\mathtt{ d}</tex>значений{{---}} несогласованность.

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

int get_min'''void''' 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; // "проталкиваем" несогласованность детям tree[2 * node + 1].d += tree[node].d<tex>\odot</tex> val; tree[2 * node + 2].d += tree[node].d; tree[node].d = 0 '''return''';

int m = push(l + rnode) ; <font color=green>/ 2;/ Обновление детей </font> int ans = min(get_min update(2 * node * 2 + 1, a, min(b, mval)), ; get_min update(2 * node * 2 + 2, max(a, m)b, b))val); <font color=green>// Пересчет значения на текущем отрезке </font> tree[node].min ans = (tree[2 * node + 1].ans;<tex>\odot</tex> tree[2 * node + 1].d) <tex>\oplus</tex> return (tree[2 * node + 2].ans<tex>\odot</tex> tree[2 * node + 2].d);

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