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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «Обычное дерево Фенвика позволяет выполнять некоторую ассоциативную, ко…»)
 
м
Строка 16: Строка 16:
  
 
<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> n </tex> элементов. Так как для каждого из <tex> O(log(n)) </tex> изменяемых элементов дерева мы совершаем дополнительно запрос суммы на отрезке(а он работает за <tex> O(log(n)) </tex> операций), то асимптотическое время работы обновления элемента ухудшается до <tex> O(log^2(n)) </tex>.

Версия 20:36, 15 июня 2011

Обычное дерево Фенвика позволяет выполнять некоторую ассоциативную, коммутативную, обратимую операцию [math] G [/math] на отрезке [math] [i; j] [/math] с изменением элементов. Описываемая модификация дает возможность отказаться от коммутативности [math] G [/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 a_i'[/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] f_j \leftarrow f_j \cdot s_{i, j}^{-1} \cdot d \cdot s_{i, j} [/math].

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