Изменения

Как и ранее, для обновления элемента в дереве нужно изменить все, что хранит результат операции с этим элементом. Но теперь нельзя просто применить операцию <tex> G </tex> (далее будем использовать мультипликативную нотацию) ко всем нужным элементам дерева. Пусть мы хотим изменить <tex> a_i </tex> на <tex> a_i' = a_i \cdot d </tex>, в данный момент обновляем элемент дерева с индексом <tex> j </tex>. Вместо <tex> a_{j \& (j + 1)} \cdot \ldots a_i \cdot d \cdot \cdot \ldots \cdot a_j </tex> мы получим <tex> a_{j \& (j + 1)} \cdot \ldots a_i \cdot \ldots \cdot a_j \cdot d </tex> (так как больше нельзя переставлять элементы местами в операции на отрезке, ответ будет неверен).

Может показаться, что этот способ не работает, так как <tex> s_i </tex>, возможно, уже было изменено, а <tex> s_j </tex> — еще нет, значит, мы удаляем не тот отрезок, который должны удалить. Убедимся, что на самом деле все обновляется правильно. Учитывая, что <tex> (x \cdot y)^{-1} = y^{-1} \cdot x^{-1} </tex>, получаем:

<tex> {s_{i, j}'}^{-1} \cdot d \cdot s_{i, j}{'} = (d^{-1} \cdot s_{i, j})^{-1} \cdot d \cdot d^{-1} \cdot s_{i, j} = s_{i, j}^{-1} \cdot d \cdot d \cdot d^{-1} \cdot s_{i, j} = s_{i, j}^{-1} \cdot d \cdot s_{i, j} </tex>, то есть элемент дерева изменяется на правильное значение.

=== Время работы ===

== Выполнение запроса ==

t_0 = a_0 & t_1 = a_0 \cdot a_1 & t_2' = a_2' & t_3' = a_0 \cdot a_1 \cdot a_2' \cdot a_3 & t_4 = a_4 \\

\end{array} </tex>