1632
правки
Изменения
м
rollbackEdits.php mass rollback
Рассмотрим в общем виде реализацию массовой операции на отрезке. Пусть необходимо отвечать на запросы относительно операции <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 ===
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);
'''return''' ans;
}
==См. также==
*[[Дерево отрезков. Построение]]
* [[Реализация запроса в дереве отрезков сверху]]
*[[Реализация запроса в дереве отрезков снизу]]
==Источники информации==
