Изменения

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

Решение — нужно удалить отрезок после изменяемого элемента, изменить элемент, после чего добавить этот отрезок снова. Пусть <tex> s_i = a_1 \circ cdot a_2 \circ cdot \ldots \circ cdot a_i </tex> — результат выполнения операции на префиксе <tex> i </tex>, ; <tex> s_{i, j} = s_i^{-1} \circ cdot s_j </tex> — результат ее выполнения на отрезке <tex> [i; j] </tex>. Тогда элемент дерева с индексом <tex> j </tex> обновляется как <tex> f_j \leftarrow f_j t_j' = t_j \circ cdot s_{i, j}^{-1} \circ cdot d \circ cdot s_{i, j} </tex>.

<tex> s_{i, j}{'} = (s_i \circ cdot d)^{-1} \circ cdot s_j = d^{-1} \circ cdot s_i^{-1} \circ cdot s_j = d^{-1} \circ cdot s_{i, j} </tex>;

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