1302
правки
Изменения
Нет описания правки
get_min(v, l, r) {
// v - текущая вершина, l и r - границы запроса
if (отрезок соответственный соответствующий v не пересекается с [l, r])
return inf // бесконечность - нейтральный элемент относительно min
if (отрезок соответственный соответствующий v содержится в [l, r])
return tree[v] + d[v]
// Раздаем детям
d[2*v+1] = d[2*v+1] + d[v] d[2*v+2] = d[2*v+2] + d[v]
d[v] = 0
// Вызываем функцию от детей
ans = min(get_min(2*v+1, l, r), get_min(2*v+2, l, r))
// Пересчитываем свое значение
T[v] = min(T[2*v+1] + d[2*v+1], T[2*v+2] + d[2*v+2])
return ans
}
}
// Раздаем детям
d[2*v+1] = d[2*v+1] + d[v] d[2*v+2] = d[2*v+2] + d[v]
d[v] = 0
// Вызываем функцию от детей
update(2*v+1, l, r, x) update(2*v+2, l, r, x)
// Пересчитываем свое значение
T[v] = min(T[2*v+1]+d[2*v+1],T[2*v+2]+d[2*v+2]) return ans
}
