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

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
(Перенаправление на Дерево Фенвика)
 
Строка 1: Строка 1:
Переименуем функцию <tt>sum()</tt> в функцию <tt>alpha()</tt>, а функцию <tt>add()</tt> &mdash; в функцию <tt>modifyAlphas()</tt>.
#REDIRECT [[Дерево Фенвика]]
 
int alpha(int r) {
    int res = 0;
    for (int i = r; i >= 0; i = (i & (i + 1)) - 1)
        res += b[i];
    return res;
}
void modifyAlphas(int pos, int val) {
    for (int i = pos; i < MAX_SIZE; i |= i + 1)
        b[i] += val;
}
 
Тогда в общем случае мы можем считать, что вызов <tt>alpha(i)</tt> возвращает результат некоторой функции <tt>&alpha;(i)</tt> (или элемент некоторого массива <tt>&alpha;[i]</tt>), а вызов <tt>modifyAlphas(pos, val)</tt> добавляет значение <tt>val</tt> ко всем <tt>&alpha;(i)</tt> (или <tt>&alpha;[i]</tt>), у которых <tt>i >= pos</tt>.
В зависимости от того, как трактовать значение <tt>&alpha;(i)</tt>, можно получить несколько применений дерева Фенвика.
Если считать, что <tt>&alpha;(i)</tt> &mdash; сумма элементов массива <tt>a[]</tt> от <tt>a[0]</tt> до <tt>a[i]</tt>, то мы получим базовую версию дерева Фенвика, в которой функция <tt>modifyAlphas()</tt> изменяет элемент массива <tt>a[]</tt>.
 
== Запрос отдельных элементов и модификация на отрезке ==
 
Пусть <tt>&alpha;(i)</tt> &mdash; значение <tt>i</tt>-го элемента массива <tt>a[]</tt>. Тогда вызов <tt>modifyAlphas(pos, val)</tt> добавит <tt>val</tt> ко всем элементам <tt>a[]</tt>, у которых <tt>i >= pos</tt>. Следовательно, чтобы увеличить только элементы с индексами от <tt>l</tt> до <tt>r</tt>, нужно вызвать <tt>modifyAlphas(l, val)</tt> и <tt>modifyAlphas(r + 1, -val)</tt>.
 
int get(int pos) {
    return alpha(pos);
}
int add(int l, int r, int val) {
    modifyAlphas(l, val);
    modifyAlphas(r + 1, -val);
}
 
== Запрос на отрезке и модификация на отрезке ==
 
Пусть используется второе дерево Фенвика, реализующее функции <tt>beta()</tt> и <tt>modifyBetas()</tt>, и пусть <tt>(&beta;(i) * i + &alpha;(i))</tt> &mdash; сумма элементов массива <tt>a[]</tt> от <tt>a[0]</tt> до <tt>a[i]</tt>.
Далее, пусть элементы массива <tt>a[]</tt> с индексами от <tt>l</tt> до <tt>r</tt> увеличились на величину <tt>val</tt>. Рассмотрим, как при этом изменится сумма элементов массива <tt>a[]</tt> от <tt>a[0]</tt> до <tt>a[i]</tt>:
* Если <tt>i < l</tt>, то сумма не изменилась, и значение <tt>(&beta;(i) * i + &alpha;(i))</tt> ей соответствует.
* Если <tt>l <= i <= r</tt>, то сумма увеличилась на <tt>(val * (i - l + 1))</tt>. Следовательно, к <tt>&beta;(i)</tt> нужно добавить <tt>val</tt>, а к <tt>&alpha;(i)</tt> &mdash; <tt>(val * (-l + 1))</tt>.
* Если <tt>i > r</tt>, то сумма увеличилась на <tt>(val * (r - l + 1))</tt>. Следовательно, <tt>&beta;(i)</tt> изменять не нужно, а к <tt>&alpha;(i)</tt> нужно добавить <tt>(val * (r - l + 1))</tt>.
 
int sum(int r) {
    return beta(r) * r + alpha(r);
}
void add(int l, int r, int val) {
    modifyBetas(l, val);
    modifyAlphas(l, val * (-l + 1));
    modifyBetas(r + 1, -val);    //modifyBetas(r + 1, 0 - val);
    modifyAlphas(r + 1, val * r); //modifyAlphas(r + 1, (val * (r - l + 1)) - (val * (-l + 1)));
}
 
== Ссылки ==
* [[Дерево Фенвика]]
* [[Варианты дерева Фенвика]]
* [http://arxiv.org/pdf/1311.6093v4.pdf Mishra P. A New Algorithm for Updating and Querying Sub-arrays of Multidimensional Arrays]
* [http://petr-mitrichev.blogspot.ru/2013/05/fenwick-tree-range-updates.html petr-mitrichev.blogspot.ru &mdash; Fenwick tree range updates]
* [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