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