Изменения

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

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

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

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

==Псевдокод в общем виде= update ===Пусть поступают запросы двух типов {{---}} поиск элемента, соответствующего операций <tex>\oplus</tex>, и массовое обновление Процедура обновления на отрезке относительно операций <tex>\odot</tex>. Используется классическая реализация дерева Данная процедура выполняет разбиение текущего отрезка с полуинтерваламина подотрезки и обновление в них несогласованности. Пусть Очень важно выполнить push как только идет рекурсивный вызов от детей, чтобы избежать некорректной обработки в детях. И так как значение в узлах дерева хранятся структуры из четырех полей:* <tex>left</tex> {{---}} левая граница полуинтерваладетях могло измениться, за который "отвечает" текущая вершина.* <tex>right</tex> {{---}} правая граница этого полуинтервала.* <tex> ans</tex> {{---}} сумма на отрезке то необходимо выполнить обновление ответа по операций операции <tex>\oplus</tex>.* <tex> d</tex> {{---}} несогласованностьна текущем отрезке.

// Процедура "проталкивания" несогласованности детям void push(int node) { 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>; // Нейтральный элемент } // Процедура ответа на множественные запросы. '''void ''' update(int node, int a, int b, int T val) { <font color=green> // val - значение, которое поступило в качестве параметра на которое нужно увеличить отрезокзапрос, a и b - границы запроса </font>

'''if ''' [l, r)<tex>\bigcap cap </tex>[a, b) == <tex> \varnothing</tex> '''return'''; '''if ''' [l, r) == <tex>\subset </tex> [a, b)

'''return''';

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

<font color=green>// Пересчитываем свое значениеПересчет значения на текущем отрезке </font>

=== query ===Получение ответа по операции <tex>\oplus</tex>. Отличие от операции обновления лишь в том, что для каждого отрезка разбиения необходимо не обновить несогласованность, а сложить по операции <tex>\oplus</ Функция ответа tex> с текущим ответом истинное значение на запросыотрезке (то есть результат сложения по операции <tex>\odot</tex> значения в вершине с несогласованностью).  int get_ans'''T''' query(int node, int a, int b) { // node - текущая вершина, a и b - границы запроса

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

int m = (l + r) / 2; int T ans = get_ans query(node * 2 + 1, a, ans(b, m)) <tex>\oplus</tex> get_ans query(node * 2 + 2, max(a, m), b));

'''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 Дерево отрезков — Википедия]