Изменения

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

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

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

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