Несогласованные поддеревья. Реализация массового обновления — различия между версиями
Gr1n (обсуждение | вклад) |
м (rollbackEdits.php mass rollback) |
||
(не показаны 22 промежуточные версии 7 участников) | |||
Строка 1: | Строка 1: | ||
− | [[Дерево отрезков. Построение|Дерево отрезков]] позволяет осуществлять | + | [[Дерево отрезков. Построение|Дерево отрезков]] позволяет осуществлять '''массовые операции''', то есть данная структура позволяет выполнять операции с несколькими подряд идущими элементами. Причем время работы, как и при других запросах, равно <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>a_i..a_j</tex> хранится несогласованность <tex>d</tex>. Если в вершине хранится истинное значение суммы, то <tex>d = \perp</tex> {{---}} нейтральный элемент относительно операции <tex>\odot</tex> (например 0 для прибавления). Для реализации операция <tex>\odot</tex> должна быть ассоциативной, и операции должны удовлетворять свойству дистрибутивности: | ||
Строка 15: | Строка 15: | ||
Рассмотрим в общем виде реализацию массовой операции на отрезке. Пусть необходимо отвечать на запросы относительно операции <tex>\oplus</tex>, а запрос массового обновления идет по операции <tex>\odot</tex>. | Рассмотрим в общем виде реализацию массовой операции на отрезке. Пусть необходимо отвечать на запросы относительно операции <tex>\oplus</tex>, а запрос массового обновления идет по операции <tex>\odot</tex>. | ||
− | Для эффективной | + | Для эффективной реализации будем использовать описанную выше структуру {{---}} несогласованные поддеревья. В каждой вершине, помимо непосредственно результата выполнения операции <tex>\oplus</tex>, храним несогласованность {{---}} величина, с которой нужно выполнить операцию <tex>\odot</tex> для всех элементов текущего отрезка. Тем самым мы сможем обрабатывать запрос массового обновления на любом подотрезке эффективно, вместо того чтобы изменять все <tex>O(N)</tex> значений. Как известно из определения несогласованных поддеревьев, в текущий момент времени не в каждой вершине дерева хранится истинное значение, однако когда мы обращаемся к текущему элементу мы работаем с верными данными. Это обеспечивается "проталкиванием" несогласованности детям (процедура push) при каждом обращений к текущей вершине. При этом после обращения к вершине необходимо пересчитать значение по операции <tex>\oplus</tex>, так как значение в детях могло измениться. |
Рассмотрим описанные выше операции более подробно. В каждом нижеприведенном псевдокоде в узлах дерева хранятся структуры из четырех полей: | Рассмотрим описанные выше операции более подробно. В каждом нижеприведенном псевдокоде в узлах дерева хранятся структуры из четырех полей: | ||
− | * <tex>left</tex> {{---}} левая граница полуинтервала, за который "отвечает" текущая вершина. | + | * <tex>\mathtt{left}</tex> {{---}} левая граница полуинтервала, за который "отвечает" текущая вершина. |
− | * <tex>right</tex> {{---}} правая граница этого полуинтервала. | + | * <tex>\mathtt{right}</tex> {{---}} правая граница этого полуинтервала. |
− | * <tex> ans</tex> {{---}} | + | * <tex>\mathtt{ ans}</tex> {{---}} результат на отрезке по операции <tex>\oplus</tex>. |
− | * <tex> d</tex> {{---}} несогласованность. | + | * <tex>\mathtt{ d}</tex> {{---}} несогласованность. |
=== push === | === push === | ||
− | + | "Проталкивание" несогласованности детям. Необходимо выполнять как только идет рекурсивный запуск от текущей вершины к её детям. Нужно это для того, чтобы в детях в момент обработки были корректные данные. | |
− | void push(int node) { | + | '''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 + 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[2 * node + 2].d = tree[2 * node + 2].d <tex>\odot</tex> tree[node].d; | ||
− | tree[node].d = <tex>\perp</tex>; // Нейтральный элемент | + | tree[node].d = <tex>\perp</tex>; <font color=green> // Нейтральный элемент </font> |
− | } | + | } |
+ | |||
=== update === | === update === | ||
− | Процедура обновления на отрезке. Данная процедура выполняет разбиение текущего отрезка на подотрезки и обновление в них несогласованности. Очень важно выполнить push как только идет рекурсивный вызов от детей, чтобы избежать некорректной обработки в детях. И так как значение в детях могло измениться, то необходимо выполнить обновление ответа по | + | Процедура обновления на отрезке. Данная процедура выполняет разбиение текущего отрезка на подотрезки и обновление в них несогласованности. Очень важно выполнить push как только идет рекурсивный вызов от детей, чтобы избежать некорректной обработки в детях. И так как значение в детях могло измениться, то необходимо выполнить обновление ответа по операции <tex>\oplus</tex> на текущем отрезке. |
− | void update(int node, int a, int b, T val) { | + | '''void''' update(int node, int a, int b, T val) { |
− | // val - значение, которое поступило в качестве параметра на запрос, a и b - границы запроса | + | <font color=green> // val - значение, которое поступило в качестве параметра на запрос, a и b - границы запроса </font> |
l = tree[node].left; | l = tree[node].left; | ||
r = tree[node].right; | r = tree[node].right; | ||
'''if''' [l, r) <tex>\cap </tex> [a, b) == <tex> \varnothing</tex> | '''if''' [l, r) <tex>\cap </tex> [a, b) == <tex> \varnothing</tex> | ||
'''return'''; | '''return'''; | ||
− | '''if''' [l, r) <tex>\ | + | '''if''' [l, r) <tex>\subset </tex> [a, b) |
tree[node].d = tree[node].d <tex>\odot</tex> val; | tree[node].d = tree[node].d <tex>\odot</tex> val; | ||
'''return'''; | '''return'''; | ||
push(node); | push(node); | ||
− | // Обновление детей | + | <font color=green>// Обновление детей </font> |
update(2 * node + 1, a, b, val); | update(2 * node + 1, a, b, val); | ||
update(2 * node + 2, 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[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); | (tree[2 * node + 2].ans <tex>\odot</tex> tree[2 * node + 2].d); | ||
Строка 55: | Строка 55: | ||
=== query === | === query === | ||
− | Получение ответа по | + | Получение ответа по операции <tex>\oplus</tex>. Отличие от операции обновления лишь в том, что для каждого отрезка разбиения необходимо не обновить несогласованность, а сложить по операции <tex>\oplus</tex> с текущим ответом истинное значение на отрезке (то есть результат сложения по операции <tex>\odot</tex> значения в вершине с несогласованностью). |
− | T query(int node, int a, int b) { | + | '''T''' query(int node, int a, int b) { |
l = tree[node].left; | l = tree[node].left; | ||
r = tree[node].right; | r = tree[node].right; | ||
− | '''if''' [l, r )<tex>\cap </tex> [a, b) == <tex> \varnothing</tex> | + | '''if''' [l, r ) <tex>\cap</tex> [a, b) == <tex> \varnothing</tex> |
'''return''' <tex>\perp</tex>; | '''return''' <tex>\perp</tex>; | ||
− | '''if''' [l, r) | + | '''if''' [l, r) <tex>\subset</tex> [a, b) |
'''return''' tree[node].ans <tex>\odot</tex> tree[node].d; | '''return''' tree[node].ans <tex>\odot</tex> tree[node].d; | ||
push(node); | push(node); | ||
− | T ans = | + | T ans = query(node * 2 + 1, a, b) <tex>\oplus</tex> |
− | + | 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[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); | (tree[2 * node + 2].ans <tex>\odot</tex> tree[2 * node + 2].d); | ||
Строка 72: | Строка 72: | ||
} | } | ||
− | == | + | ==См. также== |
+ | *[[Дерево отрезков. Построение]] | ||
+ | |||
+ | * [[Реализация запроса в дереве отрезков сверху]] | ||
+ | |||
+ | *[[Реализация запроса в дереве отрезков снизу]] | ||
+ | |||
+ | ==Источники информации== | ||
− | [http://e-maxx.ru/algo/segment_tree MAXimal :: algo :: Дерево отрезков] | + | * [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 Дерево отрезков — Википедия] | + | * [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 Дерево отрезков — Википедия] |
[[Категория: Дискретная математика и алгоритмы]] | [[Категория: Дискретная математика и алгоритмы]] | ||
[[Категория: Дерево отрезков]] | [[Категория: Дерево отрезков]] |
Текущая версия на 19:05, 4 сентября 2022
Дерево отрезков позволяет осуществлять массовые операции, то есть данная структура позволяет выполнять операции с несколькими подряд идущими элементами. Причем время работы, как и при других запросах, равно .
Несогласованные поддеревья
Сперва рассмотрим так называемые несогласованные поддеревья.
Пусть дерево отрезков хранит в вершинах результат выполнения операции
на текущем отрезке, а запрос обновления идет по операции .В несогласованном поддереве дерева отрезков в вершинах хранятся не истинные значения сумм (по операции
) на отрезках, однако гарантируется, что на запрос они отвечают верно. При этом в корне поддерева, которому соответствует отрезок хранится несогласованность . Если в вершине хранится истинное значение суммы, то — нейтральный элемент относительно операции (например 0 для прибавления). Для реализации операция должна быть ассоциативной, и операции должны удовлетворять свойству дистрибутивности:Массовое обновление
Рассмотрим в общем виде реализацию массовой операции на отрезке. Пусть необходимо отвечать на запросы относительно операции
, а запрос массового обновления идет по операции .Для эффективной реализации будем использовать описанную выше структуру — несогласованные поддеревья. В каждой вершине, помимо непосредственно результата выполнения операции
, храним несогласованность — величина, с которой нужно выполнить операцию для всех элементов текущего отрезка. Тем самым мы сможем обрабатывать запрос массового обновления на любом подотрезке эффективно, вместо того чтобы изменять все значений. Как известно из определения несогласованных поддеревьев, в текущий момент времени не в каждой вершине дерева хранится истинное значение, однако когда мы обращаемся к текущему элементу мы работаем с верными данными. Это обеспечивается "проталкиванием" несогласованности детям (процедура push) при каждом обращений к текущей вершине. При этом после обращения к вершине необходимо пересчитать значение по операции , так как значение в детях могло измениться.Рассмотрим описанные выше операции более подробно. В каждом нижеприведенном псевдокоде в узлах дерева хранятся структуры из четырех полей:
- — левая граница полуинтервала, за который "отвечает" текущая вершина.
- — правая граница этого полуинтервала.
- — результат на отрезке по операции .
- — несогласованность.
push
"Проталкивание" несогласованности детям. Необходимо выполнять как только идет рекурсивный запуск от текущей вершины к её детям. Нужно это для того, чтобы в детях в момент обработки были корректные данные.
void push(int node) { // node - текущая вершина tree[2 * node + 1].d = tree[2 * node + 1].dtree[node].d; tree[2 * node + 2].d = tree[2 * node + 2].d tree[node].d; tree[node].d = ; // Нейтральный элемент }
update
Процедура обновления на отрезке. Данная процедура выполняет разбиение текущего отрезка на подотрезки и обновление в них несогласованности. Очень важно выполнить push как только идет рекурсивный вызов от детей, чтобы избежать некорректной обработки в детях. И так как значение в детях могло измениться, то необходимо выполнить обновление ответа по операции
на текущем отрезке.void update(int node, int a, int b, T val) { // val - значение, которое поступило в качестве параметра на запрос, a и b - границы запроса l = tree[node].left; r = tree[node].right; if [l, r)[a, b) == return; if [l, r) [a, b) tree[node].d = tree[node].d val; return; push(node); // Обновление детей update(2 * node + 1, a, b, val); update(2 * node + 2, a, b, val); // Пересчет значения на текущем отрезке tree[node].ans = (tree[2 * node + 1].ans tree[2 * node + 1].d) (tree[2 * node + 2].ans tree[2 * node + 2].d); }
query
Получение ответа по операции
. Отличие от операции обновления лишь в том, что для каждого отрезка разбиения необходимо не обновить несогласованность, а сложить по операции с текущим ответом истинное значение на отрезке (то есть результат сложения по операции значения в вершине с несогласованностью).T query(int node, int a, int b) { l = tree[node].left; r = tree[node].right; if [l, r )[a, b) == return ; if [l, r) [a, b) return tree[node].ans tree[node].d; push(node); T ans = query(node * 2 + 1, a, b) query(node * 2 + 2, a, b)); tree[node].ans = (tree[2 * node + 1].ans tree[2 * node + 1].d) (tree[2 * node + 2].ans tree[2 * node + 2].d); return ans; }