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

Дерево отрезков позволяет отвечать на запросы к целым отрезкам подряд идущих элементов, причем за то же время [math]O(\log n)[/math].

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

Сперва рассмотрим так называемые несогласованные поддеревья.

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

1. [math]a \odot (b \odot c) = (a \odot b) \odot c[/math]
2. [math](a \oplus b) \odot c = (a \odot c) \oplus (b \odot c)[/math]
3. [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])
}

Ссылки

MAXimal :: algo :: Дерево отрезков

Дерево отрезков — Википедия