1632
правки
Изменения
м
Выполнение запроса делается |proof=Может показаться, что этот способ не работает, так жекак <tex> s_i </tex>, как и в обычном дереве Фенвикавозможно, уже было изменено, а <tex> s_j </tex> — еще нет, значит, мы удаляем не тот отрезок, с той лишь разницейкоторый должны удалить. Убедимся, что на самом деле все обновляется правильно. Учитывая, что теперь важен порядок операндов в операции <tex> G (x \cdot y)^{-1} = y^{-1} \cdot x^{-1} </tex>., получаем:
Как и ранее, для обновления элемента Итого в обновлённом дереве нужно изменить все, что хранит результат операции с этим элементом. Но теперь нельзя просто применить операцию <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 \ldots \cdot a_j</tex> мы получим <tex>a_{j\&(j+1)} \cdot \ldots a_i \cdot \ldots \cdot a_j \cdot a_i'</tex> (так как больше нельзя переставлять элементы местами в операции на отрезке).Фенвика всё верно:
Решение - нужно удалить отрезок после изменяемого элемента, изменить элемент, после чего добавить этот отрезок снова. Пусть, <tex> s_i = a_1 \cdot a_2 begin{array}{c||c||c||c||c} \begin{pmatrix} 1 & 0 \cdot \ldots 0 & 2 \cdot a_i </tex> - результат выполнения операции на префиксе <tex> i </tex>, <tex> s_end{i, jpmatrix} = s_i^& \begin{-pmatrix} 1& 2 \\ 0 & 2 \end{pmatrix} &\begin{pmatrix} 3 & 4 \\ 2 & 4 \end{pmatrix} &\begin{pmatrix} 12 & 38 \cdot s_j </tex> - результат ее выполнения на отрезке <tex> [i; j] </tex>. Тогда элемент дерева с индексом <tex>j</tex> обновляется как <tex> f_j \leftarrow f_j 8 & 24 \cdot s_end{i, jpmatrix}^&\begin{-pmatrix} 1 & 0 \\ 2 & 1\end{pmatrix} \\\hlinet_0 = a_0 & t_1 = a_0 \cdot a_1 & t_2' = a_2' & t_3' = a_0 \cdot a_1 \cdot d a_2' \cdot s_a_3 & t_4 = a_4 \\\end{i, jarray} </tex>==См. также==* [[Дерево Фенвика]]* [[Дерево отрезков.Построение]]
Может показаться, что этот способ не работает, так как <tex> s_i </tex>, возможно, уже было изменено, а <tex> s_j </tex> - еще нет, значит, мы удаляем не тот отрезок, который должны удалить. Убедимся, что на самом деле все обновляется правильно:==Источники информации==
<tex> s_{i, j}{'} * [http://citeseer.ist.psu.edu/viewdoc/download;jsessionid= (s_i \cdot d)^{-1} \cdot s_j F180153B9C0CD797594314B736E2CCC5?doi= d^{-10.1} \cdot s_i^{-.1} \cdot s_j .14.8917&rep=rep1&type= d^{-1} \cdot s_{i, j}<pdf Peter M. Fenwick: A new data structure for cumulative frequency]* [http://en.wikipedia.org/wiki/tex>;Fenwick_tree Wikipedia — Fenwick tree]
<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>, то есть, элемент дерева изменяется на правильное значение.[[Категория: Дискретная математика и алгоритмы]][[Категория: Дерево Фенвика]][[Категория: Структуры данных]]
rollbackEdits.php mass rollback
Обычное [[Дерево_Фенвика|дерево Фенвика]] позволяет выполнять некоторую ассоциативную, коммутативную, обратимую операцию <tex> G </tex> на отрезке <tex> [i; j] </tex> с изменением элементов. Описываемая модификация дает возможность отказаться от коммутативности <tex> G </tex>.
== Выполнение запроса Обновление элемента == Как и ранее, для обновления элемента в дереве нужно изменить все, что хранит результат операции с этим элементом. Но теперь нельзя просто применить операцию <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> (так как больше нельзя переставлять элементы местами в операции на отрезке, ответ будет неверен). Для решения этой задачи нужно удалить отрезок после изменяемого элемента, изменить элемент, после чего добавить этот отрезок снова. {{Теорема|statement=Пусть <tex> s_i = a_1 \cdot a_2 \cdot \ldots \cdot a_i </tex> — результат выполнения операции на префиксе <tex> i </tex>; <tex> s_{i, j} = s_i^{-1} \cdot s_j </tex> — результат ее выполнения на отрезке <tex> [i; j] </tex>. Тогда элемент дерева с индексом <tex> j </tex> обновляется как <tex> t_j' = t_j \cdot s_{i, j}^{-1} \cdot d \cdot s_{i, j} </tex>.
<tex> s_{i, j}' =(s_i \cdot d)^{-1} \cdot s_j = Обновление d^{-1} \cdot s_i^{-1} \cdot s_j = d^{-1} \cdot s_{i, j} </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>, то есть элемент дерева изменяется на правильное значение.}}=== Время работы ===Пусть в дереве <tex> n </tex> элементов. Так как для каждого из <tex> O(\log {n}) </tex> изменяемых элементов дерева мы совершаем дополнительно запрос суммы на отрезке(а он работает за <tex> O(\log {n}) </tex> операций), то асимптотическое время работы обновления элемента ухудшается до <tex> O(\log^2{n}) </tex>. == Пример ==Пусть есть массив из пяти матриц <tex> a </tex>: <tex> \begin{array}{c||c||c||c||c} \begin{pmatrix} 1 & 0 \\ 0 & 2 \end{pmatrix} & \begin{pmatrix} 1 & 2 \\ 0 & 1 \end{pmatrix} &\begin{pmatrix} 0 & 1 \\ 2 & 0 \end{pmatrix} &\begin{pmatrix} 0 & 2 \\ 1 & 2 \end{pmatrix} &\begin{pmatrix} 1 & 0 \\ 2 & 1 \end{pmatrix} \\\hlinea_0 & a_1 & a_2 & a_3 & a_4 \\\end{array} </tex> Пусть <tex> G </tex> — операция умножения матриц. Дерево Фенвика <tex> t </tex> выглядит так: <tex> \begin{array}{c||c||c||c||c} \begin{pmatrix} 1 & 0 \\ 0 & 2 \end{pmatrix} & \begin{pmatrix} 1 & 2 \\ 0 & 2 \end{pmatrix} &\begin{pmatrix} 0 & 1 \\ 2 & 0 \end{pmatrix} &\begin{pmatrix} 1 & 10 \\ 0 & 8 \end{pmatrix} &\begin{pmatrix} 1 & 0 \\ 2 & 1 \end{pmatrix} \\\hlinet_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> 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> После этого дерево выглядит так: <tex> \begin{array}{c||c||c||c||c} \begin{pmatrix} 1 & 0 \\ 0 & 2 \end{pmatrix} & \begin{pmatrix} 1 & 2 \\ 0 & 2 \end{pmatrix} &\begin{pmatrix} 3 & 4 \\ 2 & 4 \end{pmatrix} &\begin{pmatrix} 1 & 10 \\ 0 & 8 \end{pmatrix} &\begin{pmatrix} 1 & 0 \\ 2 & 1 \end{pmatrix} \\\hlinet_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} </tex> Рассчитаем суммы: <tex> s_2' = t_{(2 \& 3) - 1} \cdot t_2' = t_1 \cdot t_2' = \begin{pmatrix} 1 & 2 \\ 0 & 2 \end{pmatrix} \cdot \begin{pmatrix} 3 & 4 \\ 2 & 4 \end{pmatrix} = \begin{pmatrix} 7 & 12 \\ 4 & 8 \end{pmatrix} </tex> <tex> s_3 = t_3 = \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> <tex> t_3' =\begin{pmatrix} 12 & 38 \\ 8 & 24 \end{pmatrix} =a_0 \cdot a_1 \cdot a_2' \cdot a_3 </tex>
