Дерево Фенвика для некоммутативных операций — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Обновление элемента)
Строка 3: Строка 3:
 
== Обновление элемента ==
 
== Обновление элемента ==
  
Как и ранее, для обновления элемента в дереве нужно изменить все, что хранит результат операции с этим элементом. Но теперь нельзя просто применить операцию <tex> G </tex> (далее будем обозначать её как <tex> \cdot </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 d </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 d </tex> (так как больше нельзя переставлять элементы местами в операции на отрезке, ответ будет неверен).
  
 
Решение — нужно удалить отрезок после изменяемого элемента, изменить элемент, после чего добавить этот отрезок снова. Пусть <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 = 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 </tex>, возможно, уже было изменено, а <tex> s_j </tex> — еще нет, значит, мы удаляем не тот отрезок, который должны удалить. Убедимся, что на самом деле все обновляется правильно:
+
=== Доказательство ===
 +
Может показаться, что этот способ не работает, так как <tex> s_i </tex>, возможно, уже было изменено, а <tex> s_j </tex> — еще нет, значит, мы удаляем не тот отрезок, который должны удалить. Убедимся, что на самом деле все обновляется правильно. Учитывая, что <tex> (x \cdot y)^{-1} = y^{-1} \cdot x^{-1} </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}' = (s_i \cdot d)^{-1} \cdot s_j = d^{-1} \cdot s_i^{-1} \cdot s_j = d^{-1} \cdot s_{i, j} </tex>;
Строка 13: Строка 14:
 
<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> {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> 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} \\
 +
\hline
 +
a_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} \\
 +
\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> 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 t_2^{-1} \cdot d \cdot t_2 </tex>
 +
 +
<tex> t_3' = t_3 \cdot s_{2, 3}^{-1} \cdot d \cdot s_{2, 3} = t_3 \cdot (t_2' \cdot t_3)^{-1} \cdot d \cdot t_2' \cdot t_3 = t_3 \cdot t_3^{-1} \cdot (t_2')^{-1} \cdot d \cdot t_2' \cdot t_3 =  </tex>
 +
 +
=== Время работы ===
 
Пусть в дереве <tex> n </tex> элементов. Так как для каждого из <tex> O(\log(n)) </tex> изменяемых элементов дерева мы совершаем дополнительно запрос суммы на отрезке(а он работает за <tex> O(\log(n)) </tex> операций), то асимптотическое время работы обновления элемента ухудшается до <tex> O(\log^2(n)) </tex>.
 
Пусть в дереве <tex> n </tex> элементов. Так как для каждого из <tex> O(\log(n)) </tex> изменяемых элементов дерева мы совершаем дополнительно запрос суммы на отрезке(а он работает за <tex> O(\log(n)) </tex> операций), то асимптотическое время работы обновления элемента ухудшается до <tex> O(\log^2(n)) </tex>.
  

Версия 18:59, 11 июня 2012

Обычное дерево Фенвика позволяет выполнять некоторую ассоциативную, коммутативную, обратимую операцию [math] G [/math] на отрезке [math] [i; j] [/math] с изменением элементов. Описываемая модификация дает возможность отказаться от коммутативности [math] G [/math].

Обновление элемента

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

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

Доказательство

Может показаться, что этот способ не работает, так как [math] s_i [/math], возможно, уже было изменено, а [math] s_j [/math] — еще нет, значит, мы удаляем не тот отрезок, который должны удалить. Убедимся, что на самом деле все обновляется правильно. Учитывая, что [math] (x \cdot y)^{-1} = y^{-1} \cdot x^{-1} [/math], получаем:

[math] 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} [/math];

[math] {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} [/math], то есть элемент дерева изменяется на правильное значение.

Пример

Пусть есть массив из пяти матриц [math] a [/math]:

[math] \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} \\ \hline a_0 & a_1 & a_2 & a_3 & a_4 \\ \end{array} [/math]

Пусть [math] G [/math] — операция умножения матриц. Дерево Фенвика [math] t [/math] выглядит так:

[math] \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} \\ \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} [/math]

Пусть теперь [math] a_2 = a_2 \cdot d = \begin{pmatrix} 0 & 1 \\ 2 & 0 \end{pmatrix} \cdot \begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix} [/math]. Значит, надо изменить [math] t_2 [/math] и [math] t_{2 | (2 + 1)} = t_3 [/math].

[math] t_2' = t_2 \cdot s_{2, 2}^{-1} \cdot d \cdot s_{2, 2} = t_2 \cdot t_2^{-1} \cdot d \cdot t_2 [/math]

[math] t_3' = t_3 \cdot s_{2, 3}^{-1} \cdot d \cdot s_{2, 3} = t_3 \cdot (t_2' \cdot t_3)^{-1} \cdot d \cdot t_2' \cdot t_3 = t_3 \cdot t_3^{-1} \cdot (t_2')^{-1} \cdot d \cdot t_2' \cdot t_3 = [/math]

Время работы

Пусть в дереве [math] n [/math] элементов. Так как для каждого из [math] O(\log(n)) [/math] изменяемых элементов дерева мы совершаем дополнительно запрос суммы на отрезке(а он работает за [math] O(\log(n)) [/math] операций), то асимптотическое время работы обновления элемента ухудшается до [math] O(\log^2(n)) [/math].

Выполнение запроса

Выполнение запроса делается так же, как и в обычном дереве Фенвика, с той лишь разницей, что теперь важен порядок операндов в операции [math] G [/math].