1632
правки
Изменения
м
Для решения этой задачи нужно удалить отрезок после изменяемого элемента, изменить элемент, после чего добавить этот отрезок снова. Пусть <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> G </tex>.
rollbackEdits.php mass rollback
Как и ранее, для обновления элемента в дереве нужно изменить все, что хранит результат операции с этим элементом. Но теперь нельзя просто применить операцию <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=
|proof=
=== Время работы ===
Пусть в дереве <tex> n </tex> элементов. Так как для каждого из <tex> O(\log {n}) </tex> изменяемых элементов дерева мы совершаем дополнительно запрос суммы на отрезке(а он работает за <tex> O(\log {n}) </tex> операций), то асимптотическое время работы обновления элемента ухудшается до <tex> O(\log^2{n}) </tex>.
== Пример ==
==См. также==
* [[Дерево Фенвика]]
* [[Дерево отрезков. Построение]]
==Источники информации==
* [http://citeseer.ist.psu.edu/viewdoc/download;jsessionid=F180153B9C0CD797594314B736E2CCC5?doi=10.1.1.14.8917&rep=rep1&type=pdf Peter M. Fenwick: A new data structure for cumulative frequency]* [Дерево отрезковhttp://en. Построение |Дерево отрезков]wikipedia.org/wiki/Fenwick_tree Wikipedia — Fenwick tree]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Дерево Фенвика]]
[[Категория: Структуры данных]]
