Дерево Фенвика с модификацией на отрезке: различия между версиями

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
(Перенаправление на Дерево Фенвика)
 
(не показаны 4 промежуточные версии этого же участника)
Строка 1: Строка 1:
== Запрос отдельных элементов и модификация на отрезке ==
#REDIRECT [[Дерево Фенвика]]
 
Если в задаче требуется производить изменения на отрезке и возвращать значения отдельных элементов, то пусть массив <tt>a[]</tt> хранит не сами элементы, а разности текущего и предыдущего элементов. Тогда, чтобы увеличить все элементы на отрезке <tt>l..r</tt> на величину <tt>val</tt>, достаточно добавить <tt>val</tt> к <tt>a[l]</tt> и добавить <tt>-val</tt> к <tt>a[r + 1]</tt> (две операции <tt>add</tt>), а чтобы вывести фактическое значение элемента в позиции <tt>pos</tt>, достаточно вернуть сумму <tt>a[1] + a[2] + ... + a[pos]</tt> (операция <tt>sum</tt>).
 
== Запрос на отрезке и модификация на отрезке ==
 
Если в задаче требуется и подсчитывать сумму, и производить прибавление на отрезке, то поступим следующим образом. Во-первых, пусть имеют место все соображения, изложенные в предыдущем абзаце. Далее, пусть сумма на отрезке <tt>1..r</tt> выражается как <tt><b>a[r] * r - a1[r]</b></tt>. Осталось понять, как будут изменяться элементы <tt>a1[]</tt> при обновлениях на отрезках <tt>a[]</tt>.
Пусть ко всем элементам <tt>a[]</tt> на отрезке <tt>l..r</tt> добавлено значение <tt>val</tt>. Рассмотрим значение суммы элементов <tt>a[]</tt> на отрезке <tt>1..pos</tt>:
* Если <tt>pos < l</tt>, то реальная сумма не изменилась, а сумма, рассчитываемая по указанной выше формуле, также не изменилась и соответствует реальной;
* Если <tt>l <= pos <= r</tt>, то к реальной сумме добавится <tt>(val * (p - l + 1))</tt>, а к сумме, рассчитываемой по указанной ранее формуле, &mdash; <tt>(val * pos)</tt>. Чтобы расчётное значение соответствовало реальному, ко всем элементам <tt>a1[]</tt> с индексами не меньше <tt>l</tt> нужно добавить <tt>(val * (l - 1))</tt>;
* Если <tt>r < pos</tt>, то к реальной сумме добавится <tt>(val * (r - l + 1))</tt>, а к сумме, рассчитываемой по указанной ранее формуле, &mdash; ничего. Чтобы расчётное значение соответствовало реальному, от всех элементов <tt>a1[]</tt> с индексами больше <tt>r</tt> нужно отнять <tt>(val * (r - l + 1))</tt>, то есть прибавить к ним <tt>(val * (l - 1 - r))</tt>;
Можно видеть, что операции над массивом <tt>a1[]</tt> можно реализовать с помощью второго дерева Фенвика:
* Добавление значения <tt>val</tt> на отрезке <tt>l..r</tt>: <tt>updateA(l, val); updateA(r + 1, -val); updateA1(l, val * (l - 1)); updateA1(r + 1, -val * r);</tt>
* Подсчёт суммы на отрезке <tt>1..r</tt>: <tt>sumA(r) * r - sumA1(r);</tt>
 
== Ссылки ==
* [http://apps.topcoder.com/forums/?module=Thread&threadID=756271 topcoder.com &mdash; How to modify BIT to update the ranges and query the ranges?]
* [http://apps.topcoder.com/forums/?module=Thread&threadID=715842 topcoder.com &mdash; Range update in BIT]
* [http://kartikkukreja.wordpress.com/2013/12/02/range-updates-with-bit-fenwick-tree kartikkukreja.wordpress.com &mdash; Range updates with BIT / Fenwick Tree]
 
[[Category:Структуры данных для задач RSQ/RMQ]]

Текущая версия от 22:58, 22 июня 2016

Перенаправление на:

Источник — https://acm.khpnets.info/w39/index.php?title=Дерево_Фенвика_с_модификацией_на_отрезке&oldid=2049