1632
правки
Изменения
м
Так называемое "проталкиваниеПроталкивание" несогласованности детям. Необходимо выполнять как только идет рекурсивный запуск от текущей вершины к её детям. Нужно это для того, чтобы в детях в момент обработки были корректные данные.
rollbackEdits.php mass rollback
[[Дерево отрезков. Построение|Дерево отрезков]] позволяет осуществлять так называемые '''массовые операции''', то есть данная структура позволяет выполнять операции с несколькими подряд идущими элементами. Причем время работы, как и при других запросах, равно <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>\oplus</tex> на текущем отрезке.
'''void ''' update(int node, int a, int b, T val) { <font color=green> // val - значение, которое поступило в качестве параметра на запрос, a и b - границы запроса</font>
l = tree[node].left;
r = tree[node].right;
'''if''' [l, r) <tex>\cap </tex> [a, b) == <tex> \varnothing</tex>
'''return''';
'''if''' [l, r) <tex>\subseteq subset </tex> [a, b)
tree[node].d = tree[node].d <tex>\odot</tex> val;
'''return''';
push(node);
<font color=green>// Обновление детей</font>
update(2 * node + 1, a, b, val);
update(2 * node + 2, a, b, val);
<font color=green>// Пересчет значения на текущем отрезке</font>
tree[node].ans = (tree[2 * node + 1].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>\subseteq subset</tex> [a, b)
'''return''' tree[node].ans <tex>\odot</tex> tree[node].d;
push(node);
T ans = get_ans query(node * 2 + 1, a, b) <tex>\oplus</tex> get_ans 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].ans <tex>\odot</tex> tree[2 * node + 2].d);
}
==СсылкиСм. также==*[[Дерево отрезков. Построение]] * [[Реализация запроса в дереве отрезков сверху]] *[[Реализация запроса в дереве отрезков снизу]] ==Источники информации==
* [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 Дерево отрезков — Википедия]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Дерево отрезков]]
