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

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

1. [math]a \odot \perp = \perp a = a[/math]
2. [math]a \odot (b \odot с) = (a \odot b) \odot c[/math]
3. [math](a \oplus b) \odot c = (a \odot c) \oplus (b \odot c)[/math]
4. [math]c \odot (a \oplus b) = (c \odot a) \oplus (c \odot b)[/math]

Если операция [math]\odot[/math] не коммутативна, то при запросах нужно, во-первых, раздать детям несогласованность, во-вторых, вызвать функцию от детей и, в-третьих, пересчитать свое значение.

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

Пусть дерево отрезков храниться в массиве [math]T[/math]. Для реализации массового обновления будем хранить дополнительный массив несогласованностей [math]d[/math]. Истинные значения [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
}