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

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

2020-09-11T12:19:27Z

Ссылки

← Предыдущая версия		Версия от 12:19, 11 сентября 2020
Строка 119:		Строка 119:
	Теория:		Теория:
	:* [[Варианты дерева Фенвика]]		:* [[Варианты дерева Фенвика]]
	:* [http://e-maxx.ru/algo/fenwick_tree e-maxx.ru ~~—~~ Дерево Фенвика]		:* [http://e-maxx.ru/algo/fenwick_tree e-maxx.ru — Дерево Фенвика]
	:* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B5%D1%82%D0%BD%D0%B0%D1%8F_%D0%BC%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0,_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D0%B8_%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D1%8B_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85#.D0.94.D0.B5.D1.80.D0.B5.D0.B2.D0.BE_.D0.A4.D0.B5.D0.BD.D0.B2.D0.B8.D0.BA.D0.B0 neerc.ifmo.ru/wiki — Дерево Фенвика]		:* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B5%D1%82%D0%BD%D0%B0%D1%8F_%D0%BC%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0,_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D0%B8_%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D1%8B_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85#.D0.94.D0.B5.D1.80.D0.B5.D0.B2.D0.BE_.D0.A4.D0.B5.D0.BD.D0.B2.D0.B8.D0.BA.D0.B0 neerc.ifmo.ru/wiki — Дерево Фенвика]
	:* [~~http~~://brestprog.~~neocities.org~~/~~lections~~/fenwicktree.~~html brestprog~~.~~neocities~~.org ~~—~~ Дерево Фенвика]		:* [https://brestprog.by/topics/fenwicktree/ brestprog.by — Дерево Фенвика]
	:* [http://cppalgo.blogspot.ru/2011/02/fenwick-tree.html cppalgo.blogspot.com ~~—~~ Дерево Фенвика]		:* [https://algorithmica.org/ru/fenwick algorithmica.org — Дерево Фенвика]
	:* [~~http~~://~~ejudge~~.~~btty~~.su/~~bmstu~~/~~addon~~/~~docs/articles/sbory2006-fenvik~~.~~pdf~~ Лахно А. Дерево Фенвика]		:* [http://cppalgo.blogspot.ru/2011/02/fenwick-tree.html cppalgo.blogspot.com — Дерево Фенвика]
			:* [https://informatics.mccme.ru/mod/book/view.php?id=491&chapterid=182 Лахно А. Дерево Фенвика]
	Демонстрация:		Демонстрация:
	:* [~~http~~://visualgo.net/~~bit.html~~ VisuAlgo ~~— Binary Indexed~~ Tree]		:* [https://visualgo.net/en/fenwicktree VisuAlgo — Fenwick Tree]
	Код:		Код:
	:* [~~http~~://github.com/indy256/codelibrary/blob/master/~~java~~/~~src~~/~~FenwickTree~~.~~java~~ CodeLibrary ~~—~~ Fenwick tree]		:* [https://github.com/indy256/codelibrary/blob/master/cpp/structures/fenwick_tree.cpp CodeLibrary — Fenwick tree]
	:* [http://github.com/ADJA/algos/blob/master/DataStructures/FenwickTree.cpp Algos ~~—~~ Fenwick tree]		:* [https://github.com/indy256/codelibrary/blob/master/cpp/structures/fenwick_tree_interval.cpp CodeLibrary — Fenwick tree interval]
	:* [http://github.com/ADJA/algos/blob/master/DataStructures/FenwickTree2D.cpp Algos ~~—~~ Fenwick tree 2D]		:* [http://github.com/ADJA/algos/blob/master/DataStructures/FenwickTree.cpp Algos — Fenwick tree]
			:* [http://github.com/ADJA/algos/blob/master/DataStructures/FenwickTree2D.cpp Algos — Fenwick tree 2D]
	Задачи:		Задачи:
	:* [[:Категория: Задачи: Дерево Фенвика\|Задачи: Дерево Фенвика]]		:* [[:Категория: Задачи: Дерево Фенвика\|Задачи: Дерево Фенвика]]

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

Ctrlalt в 23:41, 22 июня 2016

2016-06-22T23:41:15Z

Внесённые изменения

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

2016-01-27T20:16:04Z

Ссылки

← Предыдущая версия		Версия от 20:16, 27 января 2016
Строка 74:		Строка 74:
	* [http://e-maxx.ru/algo/fenwick_tree e-maxx.ru — Дерево Фенвика]		* [http://e-maxx.ru/algo/fenwick_tree e-maxx.ru — Дерево Фенвика]
	* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B5%D1%82%D0%BD%D0%B0%D1%8F_%D0%BC%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0,_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D0%B8_%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D1%8B_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85#.D0.94.D0.B5.D1.80.D0.B5.D0.B2.D0.BE_.D0.A4.D0.B5.D0.BD.D0.B2.D0.B8.D0.BA.D0.B0 neerc.ifmo.ru/wiki — Дерево Фенвика]		* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B5%D1%82%D0%BD%D0%B0%D1%8F_%D0%BC%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0,_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D0%B8_%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D1%8B_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85#.D0.94.D0.B5.D1.80.D0.B5.D0.B2.D0.BE_.D0.A4.D0.B5.D0.BD.D0.B2.D0.B8.D0.BA.D0.B0 neerc.ifmo.ru/wiki — Дерево Фенвика]
			* [http://brestprog.neocities.org/lections/fenwicktree.html brestprog.neocities.org — Дерево Фенвика]
	* [http://cppalgo.blogspot.ru/2011/02/fenwick-tree.html cppalgo.blogspot.com — Дерево Фенвика]		* [http://cppalgo.blogspot.ru/2011/02/fenwick-tree.html cppalgo.blogspot.com — Дерево Фенвика]
	* [http://informatics.mccme.ru/course/view.php?id=18 informatics.mccme.ru — Курс «Структуры данных» — часть 6]		* [http://informatics.mccme.ru/course/view.php?id=18 informatics.mccme.ru — Курс «Структуры данных» — часть 6]

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

2015-05-21T11:31:57Z

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

← Предыдущая версия		Версия от 11:31, 21 мая 2015
Строка 34:		Строка 34:

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

			'''Наиболее распространённый подход к реализации обновления на отрезке описан в подстатье [[Дерево Фенвика с модификацией на отрезке]]'''.

			Ниже приведён другой подход, описанный М. Кормышовым ([http://habrahabr.ru/post/170933/ habrahabr.ru — Дерево Фенвика с модификацией на отрезке]).

	Если в задаче требуется и подсчитывать сумму, и производить прибавление на отрезке, то добавим массив <tt>bAdd[]</tt>, <tt>i</tt>-й элемент которого хранит значение, добавляемое ко всем элементам массива <tt>a[]</tt> на отрезке <tt>f(i)..i</tt>.		Если в задаче требуется и подсчитывать сумму, и производить прибавление на отрезке, то добавим массив <tt>bAdd[]</tt>, <tt>i</tt>-й элемент которого хранит значение, добавляемое ко всем элементам массива <tt>a[]</tt> на отрезке <tt>f(i)..i</tt>.
Строка 59:		Строка 63:
	add(l - 1, -val);		add(l - 1, -val);
	}		}

	Другой подход к реализации обновления на отрезке описан в подстатье [[Дерево Фенвика с модификацией на отрезке]].

	== Ссылки на задачи ==		== Ссылки на задачи ==

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

2015-05-21T11:29:57Z

Ссылки

← Предыдущая версия		Версия от 11:29, 21 мая 2015
Строка 73:		Строка 73:
	* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B5%D1%82%D0%BD%D0%B0%D1%8F_%D0%BC%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0,_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D0%B8_%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D1%8B_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85#.D0.94.D0.B5.D1.80.D0.B5.D0.B2.D0.BE_.D0.A4.D0.B5.D0.BD.D0.B2.D0.B8.D0.BA.D0.B0 neerc.ifmo.ru/wiki — Дерево Фенвика]		* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B5%D1%82%D0%BD%D0%B0%D1%8F_%D0%BC%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0,_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D0%B8_%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D1%8B_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85#.D0.94.D0.B5.D1.80.D0.B5.D0.B2.D0.BE_.D0.A4.D0.B5.D0.BD.D0.B2.D0.B8.D0.BA.D0.B0 neerc.ifmo.ru/wiki — Дерево Фенвика]
	* [http://cppalgo.blogspot.ru/2011/02/fenwick-tree.html cppalgo.blogspot.com — Дерево Фенвика]		* [http://cppalgo.blogspot.ru/2011/02/fenwick-tree.html cppalgo.blogspot.com — Дерево Фенвика]
	* [http://habrahabr.ru/post/170933/ habrahabr.ru — Дерево Фенвика с модификацией на отрезке]
	* [http://informatics.mccme.ru/course/view.php?id=18 informatics.mccme.ru — Курс «Структуры данных» — часть 6]		* [http://informatics.mccme.ru/course/view.php?id=18 informatics.mccme.ru — Курс «Структуры данных» — часть 6]
	* [http://ejudge.btty.su/bmstu/addon/docs/articles/sbory2006-fenvik.pdf Лахно А. Дерево Фенвика]		* [http://ejudge.btty.su/bmstu/addon/docs/articles/sbory2006-fenvik.pdf Лахно А. Дерево Фенвика]

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

2015-01-11T00:30:28Z

Ссылки

← Предыдущая версия		Версия от 00:30, 11 января 2015
Строка 79:		Строка 79:
	* [http://github.com/indy256/codelibrary/blob/master/java/src/FenwickTree.java CodeLibrary — Fenwick tree]		* [http://github.com/indy256/codelibrary/blob/master/java/src/FenwickTree.java CodeLibrary — Fenwick tree]
	* [http://github.com/ADJA/algos/blob/master/DataStructures/FenwickTree.cpp Algos — Fenwick tree]		* [http://github.com/ADJA/algos/blob/master/DataStructures/FenwickTree.cpp Algos — Fenwick tree]
			* [http://github.com/ADJA/algos/blob/master/DataStructures/FenwickTree2D.cpp Algos — Fenwick tree 2D]

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

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

2014-11-14T14:12:43Z

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

	== Ссылки ==		== Ссылки ==
			* [[Дерево Фенвика с модификацией на отрезке]]
			* [[Варианты дерева Фенвика]]
	* [http://e-maxx.ru/algo/fenwick_tree e-maxx.ru — Дерево Фенвика]		* [http://e-maxx.ru/algo/fenwick_tree e-maxx.ru — Дерево Фенвика]
	* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B5%D1%82%D0%BD%D0%B0%D1%8F_%D0%BC%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0,_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D0%B8_%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D1%8B_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85#.D0.94.D0.B5.D1.80.D0.B5.D0.B2.D0.BE_.D0.A4.D0.B5.D0.BD.D0.B2.D0.B8.D0.BA.D0.B0 neerc.ifmo.ru/wiki — Дерево Фенвика]		* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B5%D1%82%D0%BD%D0%B0%D1%8F_%D0%BC%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0,_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D0%B8_%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D1%8B_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85#.D0.94.D0.B5.D1.80.D0.B5.D0.B2.D0.BE_.D0.A4.D0.B5.D0.BD.D0.B2.D0.B8.D0.BA.D0.B0 neerc.ifmo.ru/wiki — Дерево Фенвика]

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

2014-11-14T02:13:01Z

← Предыдущая версия		Версия от 02:13, 14 ноября 2014
Строка 6:		Строка 6:
	int sum(int r) {		int sum(int r) {
	int res = 0;		int res = 0;
	for (int i = r; i > 0; i = f(i) - 1)		for (int i = r; i >= 0; i = f(i) - 1)
	res += b[i];		res += b[i];
	return res;		return res;
Строка 21:		Строка 21:
	int sum(int r) {		int sum(int r) {
	int res = 0;		int res = 0;
	for (int i = r; i > 0; i = (i & (i + 1)) - 1)		for (int i = r; i >= 0; i = (i & (i + 1)) - 1)
	res += b[i];		res += b[i];
	return res;		return res;
Строка 39:		Строка 39:
	int sum(int r) {		int sum(int r) {
	int res = 0;		int res = 0;
	for (int i = r; i > 0; i = (i & (i + 1)) - 1)		for (int i = r; i >= 0; i = (i & (i + 1)) - 1)
	res += b[i] + bAdd[i] * (i - (i & (i + 1)) + 1);		res += b[i] + bAdd[i] * (i - (i & (i + 1)) + 1);
	for (int i = (r \| (r + 1)); i < MAX_SIZE; i \|= i + 1)		for (int i = (r \| (r + 1)); i < MAX_SIZE; i \|= i + 1)
Строка 49:		Строка 49:
	}		}
	void add(int r, int val) {		void add(int r, int val) {
	for (int i = r; i > 0; i = (i & (i + 1)) - 1)		for (int i = r; i >= 0; i = (i & (i + 1)) - 1)
	bAdd[i] += val;		bAdd[i] += val;
	for (int i = (r \| (r + 1)); i < MAX_SIZE; i \|= i + 1)		for (int i = (r \| (r + 1)); i < MAX_SIZE; i \|= i + 1)
Строка 60:		Строка 60:
	}		}

	Другой подход к реализации обновления на отрезке описан в подстатье [[Дерево Фенвика с модификацией на отрезке]~~], ещё один метод описан в [http://petr-mitrichev.blogspot.ru/2013/05/fenwick-tree-range-updates.html блоге Петра Митричева~~].		Другой подход к реализации обновления на отрезке описан в подстатье [[Дерево Фенвика с модификацией на отрезке]].

	== Ссылки на задачи ==		== Ссылки на задачи ==

Ctrlalt в 00:07, 14 ноября 2014

2014-11-14T00:07:17Z

← Предыдущая версия		Версия от 00:07, 14 ноября 2014
Строка 30:		Строка 30:
	void add(int pos, int val) {		void add(int pos, int val) {
	for (int i = pos; i < MAX_SIZE; i \|= i + 1)		for (int i = pos; i < MAX_SIZE; i \|= i + 1)
	b[i] += val;		b[i] += val;
	}		}

Строка 50:		Строка 50:
	void add(int r, int val) {		void add(int r, int val) {
	for (int i = r; i > 0; i = (i & (i + 1)) - 1)		for (int i = r; i > 0; i = (i & (i + 1)) - 1)
	bAdd[i] += val;		bAdd[i] += val;
	for (int i = (r \| (r + 1)); i < MAX_SIZE; i \|= i + 1)		for (int i = (r \| (r + 1)); i < MAX_SIZE; i \|= i + 1)
	b[i] += val * (r - (i & (i + 1)) + 1);		b[i] += val * (r - (i & (i + 1)) + 1);
	}		}
	void add(int l, int r, int val) {		void add(int l, int r, int val) {

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

2014-11-13T23:27:27Z

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

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

	~~Также возможен другой~~ подход к реализации обновления на отрезке~~; он~~ описан в подстатье [[Дерево Фенвика с модификацией на отрезке]].		Другой подход к реализации обновления на отрезке описан в подстатье [[Дерево Фенвика с модификацией на отрезке]], ещё один метод описан в [http://petr-mitrichev.blogspot.ru/2013/05/fenwick-tree-range-updates.html блоге Петра Митричева].

	== Ссылки на задачи ==		== Ссылки на задачи ==