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

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

В несогласованном поддереве дерева отрезков в вершинах хранятся не истинные значения сумм на отрезках (по операции [math]\oplus[/math]). При этом в корне поддерева, которому соответствует отрезок [math]a_i..a_j[/math] хранится несогласованность [math]d[/math]. Для того чтобы узнать истинное значение нужно «собрать» все несогласованности на пути от вершины к корню дерева: [math]b_i = b'_i \odot \left(\bigodot\limits_k d_k \right)[/math]. То есть для этого необходимо, чтобы вторая операция [math]\odot[/math] была ассоциативной. Если в вершине хранится истинное значение суммы, то [math]d = \perp[/math] — нейтральный элемент относительно операции [math]\odot[/math].

Массовые операции

Рассмотрим два примера: присваивание на отрезке и прибавление на отрезке.

Присваивание

[math]a[i]..a[j] \leftarrow c[/math]

Для того, чтобы присвоить всем элементам на отрезке новое значение, его нужно, как в обычном запросе разбить на [math]log n[/math] отрезков, которые соответствуют некоторым вершинам, и в соответствующие узлы добавить несогласованность: [math]d_k \leftarrow c[/math].