Несогласованные поддеревья. Реализация массового обновления

Несогласованные поддеревья

В несогласованном поддереве дерева отрезков в вершинах хранятся не истинные значения сумм на отрезках (по операции [math]\oplus[/math]). При этом в корне поддерева, которому соответствует отрезок [math]a_i..a_j[/math] хранится несогласованность [math]d[/math]. Если в вершине хранится истинное значение суммы, то [math]d = \perp[/math] — нейтральный элемент относительно операции [math]\odot[/math]. Если операция [math]\odot[/math] не коммутативна, то нужно, во-первых, раздать детям несогласованность, во-вторых, вызвать функцию от детей и, в-третьих, пересчитать свое значение. Очень важно выполнить все три пункта.

Массовые операции на отрезке рассмотрим на примере минимума на отрезке и прибавления на отрезке.

Пусть дерево отрезков храниться в массиве T. Для реализации массового обновления будем хранить дополнительный массив несогласованностей d[]. Истинные значения [math]T'[v] = T[v] + d[v][/math].

Псевдокод (нумерация массивов с нуля, то есть корень дерева - T[0]):

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
update(v, l, r, x)
// x - сколько нужно прибавить на отрезке
    if (отрезок соответственный v не пересекается с [l, r])
        return
    if (отрезок соответственный v содержится в [l, r]) {
        d[v] = d[v] + x
        return
    }
    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