Изменения

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

Пусть в узлах дерева хранятся структуры из четырех полей:* '''void''' push(int node) { <texfont color=green>left</tex> {{/ node ---}} левая граница полуинтервала, за который "отвечает" текущая вершина.* <tex>right</tex> {{---}} правая граница этого полуинтервала.* <tex> ans</tex> {{---}} сумма на отрезке по операции <tex>\oplus</tex>.* <texfont> d</tex> {{---}} несогласованность.  // Процедура "проталкивания" несогласованности детям void push(int node) {

tree[node].d = <tex>\perp</tex>; <font color=green> // Нейтральный элемент</font> } // === update ===Процедура обновления на отрезке. Данная процедура выполняет разбиение текущего отрезка на подотрезки и обновление в них несогласованности. Очень важно выполнить push как только идет рекурсивный вызов от детей, чтобы избежать некорректной обработки в детях. И так как значение в детях могло измениться, то необходимо выполнить обновление ответа по операции <tex>\oplus</tex> на множественные запросытекущем отрезке.   '''void ''' update(int node, int a, int b, my_type T val) { <font color=green> // val - значение, которое поступило в качестве параметра на запрос, a и b - границы запроса </font>

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

'''return''';

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

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

=== query ===Получение ответа по операции <tex>\oplus</tex>. Отличие от операции обновления лишь в том, что для каждого отрезка разбиения необходимо не обновить несогласованность, а сложить по операции <tex>\oplus</ Функция ответа tex> с текущим ответом истинное значение на запросыотрезке (то есть результат сложения по операции <tex>\odot</tex> значения в вершине с несогласованностью).  my_type 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 T ans = get_ans query(node * 2 + 1, a, b) <tex>\oplus</tex> get_ans query(node * 2 + 2, a, 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 Дерево отрезков — Википедия]