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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
В несогласованном поддереве дерева отрезков в вершинах хранятся не истинные значения сумм на отрезках (по операции <tex>\oplus</tex>). При этом в корне поддерева, которому соответствует отрезок <tex>a_i..a_j</tex> хранится несогласованность <tex>d</tex>. Если в вершине хранится истинное значение суммы, то <tex>d = \perp</tex> {{---}} нейтральный элемент относительно операции <tex>\odot</tex>. Если операция <tex>\odot</tex> не коммутативна, то нужно, во-первых, раздать детям несогласованность, во-вторых, вызвать функцию от детей и, в-третьих, пересчитать свое значение. Очень важно выполнить все три пункта.  
+
В несогласованном поддереве дерева отрезков в вершинах хранятся не истинные значения сумм на отрезках (по операции <tex>\oplus</tex>). При этом в корне поддерева, которому соответствует отрезок <tex>a_i..a_j</tex> хранится несогласованность <tex>d</tex>. Если в вершине хранится истинное значение суммы, то <tex>d = \perp</tex> {{---}} нейтральный элемент относительно операции <tex>\odot</tex>. Если операция <tex>\odot</tex> не коммутативна, то при запросах нужно, во-первых, раздать детям несогласованность, во-вторых, вызвать функцию от детей и, в-третьих, пересчитать свое значение. Очень важно выполнить все три пункта.  
  
 
Массовые операции на отрезке рассмотрим на примере минимума на отрезке и прибавления на отрезке.
 
Массовые операции на отрезке рассмотрим на примере минимума на отрезке и прибавления на отрезке.

Версия 23:50, 3 мая 2011

В несогласованном поддереве дерева отрезков в вершинах хранятся не истинные значения сумм на отрезках (по операции [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
}