Изменения
→Псевдокод в общем виде
// Процедура "проталкивания" несогласованности детям
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 = 0<tex>\perp</tex>;// Нейтральный элемент
}
// Процедура ответа на множественные запросы.
return;
if [l, r) == [a, b)
tree[node].d += tree[node].d <tex>\odot</tex> val;
return;
update(2 * node + 1, a, b, val);
update(2 * node + 2, a, b, val);
// Пересчитываем свое значение tree[node].min ans = min(tree[2 * node + 1].min + ans <tex>\odot</tex> tree[2 * node + 1].d, ) <tex>\oplus</tex> (tree[2 * node + 2].min + ans <tex>\odot</tex> tree[2 * node + 2].d);
}
// Функция ответа на запросы
int getget_ans(int node, int a, int b) {
// node - текущая вершина, a и b - границы запроса
l = tree[node].left;
r = tree[node].right;
if [l, r)<tex>\bigcap </tex>[a, b) == <tex> \varnothing</tex>
return <tex>\inftyperp</tex>;
if [l, r) == [a, b)
return tree[node].min + ans <tex>\odot</tex> tree[node].d;
push(node);
int m = (l + r) / 2;
int ans = min(get_min get_ans (node * 2 + 1, a, minans(b, m)), <tex>\oplus</tex> get_min get_ans (node * 2 + 2, max(a, m), b))); // Пересчитываем свое значение tree[node].min ans = min(tree[2 * node + 1].min + ans <tex>\odot</tex> tree[2 * node + 1].d, ) <tex>\oplus</tex> (tree[2 * node + 2].min + ans <tex>\odot</tex> tree[2 * node + 2].d);
return ans;
}
