Обычное [[Дерево_Фенвика|дерево Фенвика]] позволяет выполнять некоторую ассоциативную, коммутативную, обратимую операцию <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 \ldots \cdot a_j </tex> мы получим <tex> G 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> G s_i </tex>(далее используется мультипликативная нотация) ко всем нужным элементам дерева. Пусть мы хотим изменить , возможно, уже было изменено, а <tex> a_i </tex> на <tex> a_i' = a_i \cdot d s_j </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\cdot d)^{-1} \cdot s_j </tex> = d^{- результат ее выполнения на отрезке <tex> [i; j] </tex>. Тогда элемент дерева с индексом <tex>j</tex> обновляется как <tex> f_j \leftarrow f_j 1} \cdot s_{i, j}s_i^{-1} \cdot s_j = d ^{-1} \cdot s_{i, j} </tex>.;
Может показаться, что этот способ не работает, так как <tex> s_i </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, а <tex> s_j j} </tex> - еще нет, значит, мы удаляем не тот отрезок, который должны удалитьто есть элемент дерева изменяется на правильное значение. Убедимся, что на самом деле все обновляется правильно:
Пусть в дереве <tex> s_{i, j}{'} = n </tex> элементов. Так как для каждого из <tex> O(s_i \cdot dlog(n)^{-1} ) </tex> изменяемых элементов дерева мы совершаем дополнительно запрос суммы на отрезке(а он работает за <tex> O(\cdot s_j = d^{-1} log(n)) </tex> операций), то асимптотическое время работы обновления элемента ухудшается до <tex> O(\cdot s_ilog^{-1} \cdot s_j = d^{-1} \cdot s_{i, j}2(n)) </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)) G </tex>.
