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

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

Версия 00:39, 4 мая 2011

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