333
правки
Изменения
Нет описания правки
==Массовое обновление==
Рассмотрим в общем виде реализацию массовой операции на отрезке. Пусть необходимо отвечать на запросы относительно операции <tex>\oplus</tex>, а запрос массового обновления идет по операции <tex>\odot</tex>.
Для эффективной реализаций будем использовать описанную выше структуру {{---}} несогласованные поддеревья. В каждой вершине, помимо непосредственно результата выполнения операции <tex>\oplus</tex>, храним несогласованность {{---}} величина, с которой нужно выполнить операцию <tex>\odot</tex> для всех элементов текущего отрезка. Тем самым мы сможем обрабатывать запрос массового обновления на любом подотрезке эффективно, вместо того чтобы изменять все <tex>O(N)</tex> значений. Как известно из определения несогласованных поддеревьев, в текущий момент времени не в каждой вершине дерева хранится истинное значение, однако когда мы обращаемся к текущему элементу мы работаем с верными данными. Это обеспечивается так называемым "проталкиванием" несогласованности детям (процедура push) при каждом обращений к текущей вершине. При этом после обращения к вершине необходимо пересчитать значение по операции <tex>\oplus</tex>, так как значение в детях могло измениться.
=== push ===
Так называемое "проталкиваниемпроталкивание" несогласованности детям. Необходимо выполнять как только идет рекурсивный запуск от текущей вершины к её детям. Нужно это для того, чтобы в детях в момент обработки были корректные данные.
void push(int node) {
'''if''' [l, r) <tex>\cap </tex> [a, b) == <tex> \varnothing</tex>
return;
'''if''' [l, r) <tex>\subset subseteq </tex> [a, b)
tree[node].d = tree[node].d <tex>\odot</tex> val;
return;
'''if''' [l, r )<tex>\cap </tex> [a, b) == <tex> \varnothing</tex>
return <tex>\perp</tex>;
'''if''' [l, r) <tex>\subset subseteq </tex> [a, b)
return tree[node].ans <tex>\odot</tex> tree[node].d;
push(node);
