Дерево Фенвика с модификацией на отрезке - История изменений

Ctrlalt: Перенаправление на Дерево Фенвика

2016-06-22T22:58:39Z

← Предыдущая версия		Версия от 22:58, 22 июня 2016
Строка 1:		Строка 1:
	~~Переименуем функцию <tt>sum()</tt> в функцию <tt>alpha()</tt>, а функцию <tt>add()</tt> — в функцию <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>α(i)</tt> (или элемент некоторого массива <tt>α[i]</tt>), а вызов <tt>modifyAlphas(pos, val)</tt> добавляет значение <tt>val</tt> ко всем <tt>α(i)</tt> (или <tt>α[i]</tt>), у которых <tt>i >= pos</tt>.
	В зависимости от того, как трактовать значение <tt>α(i)</tt>, можно получить несколько применений дерева Фенвика.
	Если считать, что <tt>α(i)</tt> — сумма элементов массива <tt>a[]</tt> от <tt>a[0]</tt> до <tt>a[i]</tt>, то мы получим базовую версию дерева Фенвика, в которой функция <tt>modifyAlphas()</tt> изменяет элемент массива <tt>a[]</tt>.

	~~== Запрос отдельных элементов и модификация на отрезке ==~~

	Пусть <tt>α(i)</tt> — значение <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>(β(i) * i + α(i))</tt> — сумма элементов массива <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>(β(i) * i + α(i))</tt> ей соответствует.
	* Если <tt>l <= i <= r</tt>, то сумма увеличилась на <tt>(val * (i - l + 1))</tt>. Следовательно, к <tt>β(i)</tt> нужно добавить <tt>val</tt>, а к <tt>α(i)</tt> — <tt>(val * (-l + 1))</tt>.
	* Если <tt>i > r</tt>, то сумма увеличилась на <tt>(val * (r - l + 1))</tt>. Следовательно, <tt>β(i)</tt> изменять не нужно, а к <tt>α(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 — Fenwick tree range updates]
	* [http://apps.topcoder.com/forums/?module=Thread&threadID=756271 topcoder.com — How to modify BIT to update the ranges and query the ranges?]
	* [http://apps.topcoder.com/forums/?module=Thread&threadID=715842 topcoder.com — Range update in BIT]
	* [http://kartikkukreja.wordpress.com/2013/12/02/range-updates-with-bit-fenwick-tree kartikkukreja.wordpress.com — Range updates with BIT / Fenwick Tree]

	~~[[Category:Структуры данных для задач RSQ/RMQ~~]]

Ctrlalt: /* Ссылки */

2015-03-07T14:42:37Z

Ссылки

← Предыдущая версия		Версия от 14:42, 7 марта 2015
Строка 52:		Строка 52:
	* [[Дерево Фенвика]]		* [[Дерево Фенвика]]
	* [[Варианты дерева Фенвика]]		* [[Варианты дерева Фенвика]]
			* [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 — Fenwick tree range updates]		* [http://petr-mitrichev.blogspot.ru/2013/05/fenwick-tree-range-updates.html petr-mitrichev.blogspot.ru — Fenwick tree range updates]
	* [http://apps.topcoder.com/forums/?module=Thread&threadID=756271 topcoder.com — How to modify BIT to update the ranges and query the ranges?]		* [http://apps.topcoder.com/forums/?module=Thread&threadID=756271 topcoder.com — How to modify BIT to update the ranges and query the ranges?]

Ctrlalt в 14:12, 14 ноября 2014

2014-11-14T14:12:13Z

← Предыдущая версия		Версия от 14:12, 14 ноября 2014
Строка 50:		Строка 50:

	== Ссылки ==		== Ссылки ==
			* [[Дерево Фенвика]]
			* [[Варианты дерева Фенвика]]
	* [http://petr-mitrichev.blogspot.ru/2013/05/fenwick-tree-range-updates.html petr-mitrichev.blogspot.ru — Fenwick tree range updates]		* [http://petr-mitrichev.blogspot.ru/2013/05/fenwick-tree-range-updates.html petr-mitrichev.blogspot.ru — Fenwick tree range updates]
	* [http://apps.topcoder.com/forums/?module=Thread&threadID=756271 topcoder.com — How to modify BIT to update the ranges and query the ranges?]		* [http://apps.topcoder.com/forums/?module=Thread&threadID=756271 topcoder.com — How to modify BIT to update the ranges and query the ranges?]

Ctrlalt в 02:03, 14 ноября 2014

2014-11-14T02:03:42Z

← Предыдущая версия		Версия от 02:03, 14 ноября 2014
Строка 1:		Строка 1:
			Переименуем функцию <tt>sum()</tt> в функцию <tt>alpha()</tt>, а функцию <tt>add()</tt> — в функцию <tt>modifyAlphas()</tt>.

			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>α(i)</tt> (или элемент некоторого массива <tt>α[i]</tt>), а вызов <tt>modifyAlphas(pos, val)</tt> добавляет значение <tt>val</tt> ко всем <tt>α(i)</tt> (или <tt>α[i]</tt>), у которых <tt>i >= pos</tt>.
			В зависимости от того, как трактовать значение <tt>α(i)</tt>, можно получить несколько применений дерева Фенвика.
			Если считать, что <tt>α(i)</tt> — сумма элементов массива <tt>a[]</tt> от <tt>a[0]</tt> до <tt>a[i]</tt>, то мы получим базовую версию дерева Фенвика, в которой функция <tt>modifyAlphas()</tt> изменяет элемент массива <tt>a[]</tt>.

	== Запрос отдельных элементов и модификация на отрезке ==		== Запрос отдельных элементов и модификация на отрезке ==

	Если в задаче требуется производить изменения на отрезке и возвращать значения отдельных элементов, то пусть массив <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>α(i)</tt> — значение <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>~~1..r~~</tt> ~~выражается как~~ <tt~~><b~~>a[~~r] * r - a1[r~~]~~</b>~~</tt>~~. Осталось понять, как будут изменяться элементы~~ <tt>a1[]</tt> ~~при обновлениях на отрезках~~ <tt>a[]</tt>.		Пусть используется второе дерево Фенвика, реализующее функции <tt>beta()</tt> и <tt>modifyBetas()</tt>, и пусть <tt>(β(i) * i + α(i))</tt> — сумма элементов массива <tt>a[]</tt> от <tt>a[0]</tt> до <tt>a[i]</tt>.
	~~Пусть ко всем элементам~~ <tt>a[]</tt> ~~на отрезке~~ <tt>l..r</tt> ~~добавлено значение~~ <tt>val</tt>. Рассмотрим ~~значение суммы~~ элементов <tt>a[]</tt> ~~на отрезке~~ <tt>~~1..pos~~</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>~~pos~~ < l</tt>, то ~~реальная~~ сумма не изменилась, ~~а сумма, рассчитываемая по указанной выше формуле, также не изменилась~~ и соответствует ~~реальной;~~		* Если <tt>i < l</tt>, то сумма не изменилась, и значение <tt>(β(i) * i + α(i))</tt> ей соответствует.
	* Если <tt>l <= ~~pos~~ <= r</tt>, то ~~к реальной сумме добавится~~ <tt>(val * (~~pos~~ - l + 1))</tt>, а к ~~сумме, рассчитываемой по указанной ранее формуле, —~~ <tt>(~~val * pos~~)</tt>~~. Чтобы расчётное значение соответствовало реальному, ко всем элементам~~ <tt>~~a1[]~~</tt> ~~с индексами не меньше~~ <tt>l</tt> ~~нужно добавить~~ <tt>(val * (l - 1))</tt>;		* Если <tt>l <= i <= r</tt>, то сумма увеличилась на <tt>(val * (i - l + 1))</tt>. Следовательно, к <tt>β(i)</tt> нужно добавить <tt>val</tt>, а к <tt>α(i)</tt> — <tt>(val * (-l + 1))</tt>.
	* Если <tt>r ~~< pos~~</tt>, то ~~к реальной сумме добавится~~ <tt>(val * (r - l + 1))</tt>~~, а к сумме, рассчитываемой по указанной ранее формуле, — ничего~~. ~~Чтобы расчётное значение соответствовало реальному~~, ~~от всех элементов~~ <tt>~~a1[]~~</tt> ~~с индексами больше~~ <tt>r</tt> нужно ~~отнять~~ <tt>(val * (r - l + 1))</tt>~~, то есть прибавить к ним <tt>~~(~~val~~ * (~~l - 1 -~~ r)~~)</tt>~~;		* Если <tt>i > r</tt>, то сумма увеличилась на <tt>(val * (r - l + 1))</tt>. Следовательно, <tt>β(i)</tt> изменять не нужно, а к <tt>α(i)</tt> нужно добавить <tt>(val * (r - l + 1))</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>~~		int sum(int r) {
	* ~~Подсчёт суммы на отрезке <tt>1..~~r</~~tt>: <tt>sumA~~(r) * r - ~~sumA1~~(r);~~</tt>~~		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://petr-mitrichev.blogspot.ru/2013/05/fenwick-tree-range-updates.html petr-mitrichev.blogspot.ru — Fenwick tree range updates]
	* [http://apps.topcoder.com/forums/?module=Thread&threadID=756271 topcoder.com — How to modify BIT to update the ranges and query the ranges?]		* [http://apps.topcoder.com/forums/?module=Thread&threadID=756271 topcoder.com — How to modify BIT to update the ranges and query the ranges?]
	* [http://apps.topcoder.com/forums/?module=Thread&threadID=715842 topcoder.com — Range update in BIT]		* [http://apps.topcoder.com/forums/?module=Thread&threadID=715842 topcoder.com — Range update in BIT]

Ctrlalt: /* Запрос на отрезке и модификация на отрезке */

2014-11-13T23:48:50Z

Запрос на отрезке и модификация на отрезке

← Предыдущая версия		Версия от 23:48, 13 ноября 2014
Строка 8:		Строка 8:
	Пусть ко всем элементам <tt>a[]</tt> на отрезке <tt>l..r</tt> добавлено значение <tt>val</tt>. Рассмотрим значение суммы элементов <tt>a[]</tt> на отрезке <tt>1..pos</tt>:		Пусть ко всем элементам <tt>a[]</tt> на отрезке <tt>l..r</tt> добавлено значение <tt>val</tt>. Рассмотрим значение суммы элементов <tt>a[]</tt> на отрезке <tt>1..pos</tt>:
	* Если <tt>pos < l</tt>, то реальная сумма не изменилась, а сумма, рассчитываемая по указанной выше формуле, также не изменилась и соответствует реальной;		* Если <tt>pos < l</tt>, то реальная сумма не изменилась, а сумма, рассчитываемая по указанной выше формуле, также не изменилась и соответствует реальной;
	* Если <tt>l <= pos <= r</tt>, то к реальной сумме добавится <tt>(val * (p - l + 1))</tt>, а к сумме, рассчитываемой по указанной ранее формуле, — <tt>(val * pos)</tt>. Чтобы расчётное значение соответствовало реальному, ко всем элементам <tt>a1[]</tt> с индексами не меньше <tt>l</tt> нужно добавить <tt>(val * (l - 1))</tt>;		* Если <tt>l <= pos <= r</tt>, то к реальной сумме добавится <tt>(val * (pos - l + 1))</tt>, а к сумме, рассчитываемой по указанной ранее формуле, — <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>, а к сумме, рассчитываемой по указанной ранее формуле, — ничего. Чтобы расчётное значение соответствовало реальному, от всех элементов <tt>a1[]</tt> с индексами больше <tt>r</tt> нужно отнять <tt>(val * (r - l + 1))</tt>, то есть прибавить к ним <tt>(val * (l - 1 - r))</tt>;		* Если <tt>r < pos</tt>, то к реальной сумме добавится <tt>(val * (r - l + 1))</tt>, а к сумме, рассчитываемой по указанной ранее формуле, — ничего. Чтобы расчётное значение соответствовало реальному, от всех элементов <tt>a1[]</tt> с индексами больше <tt>r</tt> нужно отнять <tt>(val * (r - l + 1))</tt>, то есть прибавить к ним <tt>(val * (l - 1 - r))</tt>;
	Можно видеть, что операции над массивом <tt>a1[]</tt> можно реализовать с помощью второго дерева Фенвика:		Можно видеть, что операции над массивом <tt>a1[]</tt> можно реализовать с помощью второго дерева Фенвика:

Ctrlalt: /* Ссылки */

2014-11-13T23:27:17Z

Ссылки

← Предыдущая версия		Версия от 23:27, 13 ноября 2014
Строка 15:		Строка 15:

	== Ссылки ==		== Ссылки ==
			* [http://apps.topcoder.com/forums/?module=Thread&threadID=756271 topcoder.com — How to modify BIT to update the ranges and query the ranges?]
			* [http://apps.topcoder.com/forums/?module=Thread&threadID=715842 topcoder.com — Range update in BIT]
	* [http://kartikkukreja.wordpress.com/2013/12/02/range-updates-with-bit-fenwick-tree kartikkukreja.wordpress.com — Range updates with BIT / Fenwick Tree]		* [http://kartikkukreja.wordpress.com/2013/12/02/range-updates-with-bit-fenwick-tree kartikkukreja.wordpress.com — Range updates with BIT / Fenwick Tree]

	[[Category:Структуры данных для задач RSQ/RMQ]]		[[Category:Структуры данных для задач RSQ/RMQ]]

Ctrlalt: Новая страница: «== Запрос отдельных элементов и модификация на отрезке == Если в задаче требуется произво…»

2014-09-30T01:48:47Z

Новая страница: «== Запрос отдельных элементов и модификация на отрезке == Если в задаче требуется произво…»

Новая страница

== Запрос отдельных элементов и модификация на отрезке ==

Если в задаче требуется производить изменения на отрезке и возвращать значения отдельных элементов, то пусть массив <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>, а к сумме, рассчитываемой по указанной ранее формуле, — <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>, а к сумме, рассчитываемой по указанной ранее формуле, — ничего. Чтобы расчётное значение соответствовало реальному, от всех элементов <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://kartikkukreja.wordpress.com/2013/12/02/range-updates-with-bit-fenwick-tree kartikkukreja.wordpress.com — Range updates with BIT / Fenwick Tree]

[[Category:Структуры данных для задач RSQ/RMQ]]