418
правок
Изменения
Нет описания правки
<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>. == Выполнение запроса == Выполнение запроса делается так же, как и в обычном дереве Фенвика, с той лишь разницей, что теперь важен порядок операндов в операции <tex> G </tex>. == Пример ===
Пусть есть массив из пяти матриц <tex> a </tex>:
\end{array} </tex>
Пусть теперь <tex> a_2 ' = a_2 \cdot d = \begin{pmatrix} 0 & 1 \\ 2 & 0 \end{pmatrix} \cdot \begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix} </tex>. Значит, надо изменить <tex> t_2 </tex> и <tex> t_{2 | (2 + 1)} = t_3 </tex>.
<tex> t_2' = t_2 \cdot s_{2, 2}^{-1} \cdot d \cdot s_{2, 2} = t_2 \cdot (s_2^{-1} \cdot s_2)^{-1} \cdot d \cdot (t_2^{-1} \cdot t_2) = t_2 \cdot d = a_2' </tex>
\begin{pmatrix} 1 & 0 \\ 2 & 1 \end{pmatrix} \\
\hline
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>
Пересчитаем <tex> t_3' </tex>: <tex> t_3' = t_3 \cdot s_{2, 3}^{-1} \cdot d \cdot s_{2, 3} = t_3 \cdot (s_2'^{-1} \cdot s_3)^{-1} \cdot d \cdot </tex> Рассчитаем суммы: <tex> s_2'^{-1} \cdot s_3 = t_3 \cdot s_3^{-1} \cdot s_2' \cdot d \cdot s_2'^t_{-1} \cdot s_3 = \\ = t_3 \cdot (a_0 2 \cdot a_1 \cdot a_2 \cdot a_3& 3)^{-1} \cdot (a_0 \cdot a_1 \cdot a_2t_2') \cdot d \cdot (a_0 \cdot a_1 = t_1 \cdot a_2t_2')^{-1} \cdot (a_0 \cdot a_1 \cdot a_2 \cdot a_3) = \\ = \begin{pmatrix} 1 & 10 2 \\ 0 & 8 2 \end{pmatrix} \cdot \begin{pmatrix} 1 & 10 \\ 0 & 8 \end{pmatrix}^{-1} \cdot \begin{pmatrix} 7 3 & 12 \\ 4 & 8 \end{pmatrix} \cdot \begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix} = \begin{pmatrix} 7 & 12 \\ 4 & 8 \end{pmatrix}^{-1} \cdot \begin{pmatrix} 1 & 10 \\ 0 & 8 \end{pmatrix} </tex>
<tex> s_{2, 3} =s_2'^{-1} \cdot s_3 = Выполнение запроса ==\begin{pmatrix} 1 & -2 \\ -0.5 & 2 \end{pmatrix} </tex>
