689
правок
Изменения
Новая страница: «Обычное дерево Фенвика позволяет выполнять некоторую ассоциативную, ко…»
Обычное [[Дерево_Фенвика|дерево Фенвика]] позволяет выполнять некоторую ассоциативную, коммутативную, обратимую операцию <tex> G </tex> на отрезке <tex> [i; j] </tex> с изменением элементов. Описываемая модификация дает возможность отказаться от коммутативности <tex> G </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 \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 \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> f_j \leftarrow f_j \cdot s_{i, j}^{-1} \cdot d \cdot s_{i, j} </tex>.
Может показаться, что этот способ не работает, так как <tex> s_i </tex>, возможно, уже было изменено, а <tex> s_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> 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 \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 \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> f_j \leftarrow f_j \cdot s_{i, j}^{-1} \cdot d \cdot s_{i, j} </tex>.
Может показаться, что этот способ не работает, так как <tex> s_i </tex>, возможно, уже было изменено, а <tex> s_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>, то есть, элемент дерева изменяется на правильное значение.
