Несогласованные поддеревья. Реализация массового обновления — различия между версиями
м (rollbackEdits.php mass rollback) |
|||
(не показаны 72 промежуточные версии 12 участников) | |||
Строка 1: | Строка 1: | ||
− | + | [[Дерево отрезков. Построение|Дерево отрезков]] позволяет осуществлять '''массовые операции''', то есть данная структура позволяет выполнять операции с несколькими подряд идущими элементами. Причем время работы, как и при других запросах, равно <tex>O(\log n)</tex>. | |
− | #<tex>a \odot (b \odot | + | ==Несогласованные поддеревья== |
+ | Сперва рассмотрим так называемые '''несогласованные поддеревья'''. | ||
+ | |||
+ | Пусть дерево отрезков хранит в вершинах результат выполнения операции <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>a \odot (b \odot c) = (a \odot b) \odot c</tex> | ||
#<tex>(a \oplus b) \odot c = (a \odot c) \oplus (b \odot c)</tex> | #<tex>(a \oplus b) \odot c = (a \odot c) \oplus (b \odot c)</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>\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>\subset</tex> [a, b) | ||
+ | '''return''' tree[node].ans <tex>\odot</tex> tree[node].d; | ||
+ | push(node); | ||
+ | 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[2 * node + 2].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 Дерево отрезков — Википедия] | ||
+ | |||
+ | [[Категория: Дискретная математика и алгоритмы]] | ||
+ | [[Категория: Дерево отрезков]] |
Текущая версия на 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; }