689
правок
Изменения
м
Нет описания правки
<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>, то есть, элемент дерева изменяется на правильное значение.
Пусть в дереве <tex> n </tex> элементов. Так как для каждого из <tex> O(log(n)) </tex> изменяемых элементов дерева мы совершаем дополнительно запрос суммы на отрезке(а он работает за <tex> O(log(n)) </tex> операций), то асимптотическое время работы обновления элемента ухудшается до <tex> O(log^2(n)) </tex>.
