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