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