А ответ же на запрос по операции <tex>\oplus</tex> реализуется почти так же, как и в случае без массовых обновлений. Отличие лишь в том, что следует во-первых не забыть раздать детям несогласованность, и во-вторых пересчитать свое значение.
Таким образом Рассмотрим описанные выше операции более подробно. В каждом нижеприведенном псевдокоде в обоих запросах очень важно протолкнуть узлах дерева хранятся структуры из четырех полей:* <tex>left</tex> {{---}} левая граница полуинтервала, за который "отвечает" текущая вершина.* <tex>right</tex> {{---}} правая граница этого полуинтервала.* <tex> ans</tex> {{---}} сумма на отрезке по операции <tex>\oplus</tex>.* <tex> d</tex> {{---}} несогласованность. === push ===Так называемое "проталкиванием" несогласованности детям. Необходимо выполнять как только идет рекурсивный запуск от текущей вершины к её детям несогласованность. Нужно это для того, вызвать функцию чтобы в детях в момент обработки были корректные данные. void push(int node) { // node - текущая вершина 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>; // Нейтральный элемент } === update ===Процедура обновления на отрезке. Данная процедура выполняет разбиение текущего отрезка на подотрезки и обновление в них несогласованности. Очень важно выполнить push как только идет рекурсивный вызов от детей , чтобы избежать некорректной обработки в детях. И так как значение в детях могло измениться, то необходимо выполнить обновление ответа по операций <tex>\oplus</tex> на текущем отрезке. void update(int node, int a, int b, my_type val) { // val - значение, которое поступило в качестве параметра на запрос, a иb - границы запроса l = tree[node].left; r = tree[node].right; '''if''' [l, r) <tex>\bigcap </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); // Обновление детей update(2 * node + 1, a, b, val); update(2 * node + 2, a, наконецb, пересчитать val); // Пересчет значения на текущем отрезке 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); }=== get_ans ===Получение ответа по операций <tex>\oplus</tex>. Отличие от операций обновления лишь в том, что для каждого отрезка разбиения необходимо не обновить несогласованность, а сложить по операций <tex>\oplus</tex> с текущим ответом истинное значение на отрезке (то есть результат сложения по операций <tex>\odot</tex> значения в текущей вершинес несогласованностью). my_type get_ans(int node, int a, int b) { l = tree[node].left; r = tree[node].right; '''if''' [l, r )<tex>\bigcap </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); int ans = get_ans (node * 2 + 1, a, b) <tex>\oplus</tex> get_ans (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; }
==Псевдокод в общем виде==
