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

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:07:22Z

rollbackEdits.php mass rollback

194.88.143.66 в 06:18, 1 сентября 2022

2022-09-01T06:18:51Z

Mervap в 07:43, 21 апреля 2018

2018-04-21T07:43:11Z

Shersh в 07:26, 8 июня 2015

2015-06-08T07:26:23Z

Shersh: /* Обобщение на большие размерности */

2015-06-08T07:25:39Z

‎Обобщение на большие размерности

Shersh в 07:25, 8 июня 2015

2015-06-08T07:25:11Z

Roman в 06:01, 8 июня 2015

2015-06-08T06:01:13Z

Roman в 18:16, 7 июня 2015

2015-06-07T18:16:07Z

Roman в 18:13, 7 июня 2015

2015-06-07T18:13:53Z

Roman в 21:45, 4 июня 2015

2015-06-04T21:45:05Z

← Предыдущая		Версия 16:07, 4 сентября 2022
Строка 1:		Строка 1:
−	~~{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"~~
−	\|+
−	~~\|-align="center"~~
−	~~\|'''НЕТ ВОЙНЕ'''~~
−	~~\|-style="font-size: 16px;"~~
−	\|
−	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
−
−	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
−
−	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
−
−	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
−
−	~~''Антивоенный комитет России''~~
−	~~\|-style="font-size: 16px;"~~
−	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
−	~~\|-style="font-size: 16px;"~~
−	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
−	\|}
−
	{{Определение		{{Определение
	\|definition=		\|definition=

← Предыдущая		Версия 06:18, 1 сентября 2022
Строка 1:		Строка 1:
		+	{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
		+	\|+
		+	\|-align="center"
		+	\|'''НЕТ ВОЙНЕ'''
		+	\|-style="font-size: 16px;"
		+	\|
		+	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
		+
		+	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
		+
		+	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
		+
		+	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
		+
		+	''Антивоенный комитет России''
		+	\|-style="font-size: 16px;"
		+	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
		+	\|-style="font-size: 16px;"
		+	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
		+	\|}
		+
	{{Определение		{{Определение
	\|definition=		\|definition=

@@ Строка 45: / Строка 45: @@
 ====Обобщение на большие размерности====
 Дерево Фенвика относится к структурам данных, требующим малое количество дополнительной памяти. В комбинации с простым представлением тривиального случая данной структуры это дает возможность легко повышать размерность дерева Фенвика, в котором в ячейках какого-то фиксированного уровня будет находиться дерево меньшей размерности. Для его реализации нам достаточно во всех операциях для каждой новой размерности просто добавить вложенный цикл, пробегающий в ней соответствующие индексы.
 ==Источники информации==

@@ Строка 45: / Строка 45: @@
 ====Обобщение на большие размерности====
 Дерево Фенвика относится к структурам данных, требующим малое количество дополнительной памяти. В комбинации с простым представлением тривиального случая данной структуры это дает возможность легко повышать размерность дерева Фенвика, в котором в ячейках какого-то фиксированного уровня будет находиться дерево меньшей размерности. Для его реализации нам достаточно во всех операциях для каждой новой размерности просто добавить вложенный цикл, пробегающий в ней соответствующие индексы.
 ==Источники информации==
 *[https://www.topcoder.com/community/data-science/data-science-tutorials/binary-indexed-trees/ Topcoder {{---}} Binary Indexed Trees]
 [[Категория: Дискретная математика и алгоритмы]]
 [[Категория: Модификации структур данных]]

@@ Строка 44: / Строка 44: @@
 ====Обобщение на большие размерности====
-Дерево Фенвика относится к структурам данных, не требующим дополнительной памяти. В комбинации с простым представлением тривиального случая данной структуры это дает возможность легко повышать размерность дерева Фенвика, в котором в ячейках какого-то фиксированного уровня будет находиться дерево меньшей размерности. Для его реализации нам достаточно во всех операциях для каждой новой размерности просто добавить вложенный цикл, пробегающий в ней соответствующие индексы.
+Дерево Фенвика относится к структурам данных, требующим малое количество дополнительной памяти. В комбинации с простым представлением тривиального случая данной структуры это дает возможность легко повышать размерность дерева Фенвика, в котором в ячейках какого-то фиксированного уровня будет находиться дерево меньшей размерности. Для его реализации нам достаточно во всех операциях для каждой новой размерности просто добавить вложенный цикл, пробегающий в ней соответствующие индексы.
 ==См. также==
 *[http://e-maxx.ru/algo/fenwick_tree Дерево Фенвика]

@@ Строка 11: / Строка 11: @@
 ==Пример задачи для двумерного случая==
 Пусть имеем набор точек на плоскости с неотрицательными координатами. Определены 3 операции:
 # добавить точку в <tex>(x, y)</tex>;
@@ Строка 21: / Строка 20: @@
 Добавляя точку вызовем <tex>\mathrm{inc}(x, y, 1)</tex>, а удаляя <tex>\mathrm{inc}(x, y, -1)</tex>. Таким образом запрос <tex>\mathrm{sum}(x, y)</tex> дает количество точек в прямоугольнике.
 ==Псевдокод==
-t {{---}} массив, в котором хранится дерево Фенвика.
+<tex>\mathtt{t}</tex> {{---}} массив, в котором хранится дерево Фенвика.
 <code style = "display: inline-block;">
   '''int''' sum(x: '''int''', y: '''int'''):

@@ Строка 5: / Строка 5: @@
 # выполнять некоторую ассоциативную, коммутативную, обратимую операцию <tex> G </tex> на k-мерном прямоугольнике <tex> [i_1, \ldots ,i_k] </tex>;<br/> где n - максимальное значение для каждой координаты.
 }}
-Рассмотрим для начала дерево Фенвика на примере k-мерного массива с k = 2, а затем посмотрим, как можно обобщить его на большие размерности.
+Рассмотрим для начала дерево Фенвика на примере k-мерного массива с <tex>k = 2</tex>, а затем посмотрим, как можно обобщить его на большие размерности.
 Пусть дан массив <tex> A </tex> из <tex> n \times m </tex> элементов: <tex> a_{i,j}</tex>.<br/>
-Деревом Фенвика будем называть массив <tex> T </tex> из <tex> n \times m </tex> элементов: <tex> T_{i,j} = \sum\limits_{k = F(i)}^{i} \sum\limits_{q = F(j)}^{j}a_{k,q}</tex>, где <tex> F(i) = i \& (i + 1) </tex>, как и в одномерном [[дерево Фенвика|дереве Фенвика]].
+Деревом Фенвика будем называть массив <tex> T </tex> из <tex> n \times m </tex> элементов: <tex> T_{i,j} = \sum\limits_{k = F(i)}^{i} \sum\limits_{q = F(j)}^{j}a_{k,q}</tex>, где <tex>F(i) = i\; \&\; (i + 1)</tex>, как и в одномерном [[дерево Фенвика|дереве Фенвика]].
 ==Пример задачи для двумерного случая==
-[[Файл:example42.gif |thumb|600px|right|Пример дерева Фенвика <tex>(16 \times 8)</tex>. Синим обозначены элементы, которые обновятся при изменении ячейки <tex>(5, 3)</tex>. Чтобы обновить элемент <tex>(X, Y)</tex>, по первой координате нам надо зайти во все столбцы(деревья по второй координате), находящиеся левее <tex>X</tex> и на одной горизонтальной линии с ним, и в каждом из них обновить все ячейки под <tex>Y</tex>(в рамках обозначений нашего рисунка).]]
+[[Файл:example42.gif |thumb|600px|right|Пример дерева Фенвика <tex>(16 \times 8)</tex>. Синим обозначены элементы, которые обновятся при изменении ячейки <tex>(5, 3)</tex>. Чтобы обновить элемент <tex>(X, Y)</tex>, по первой координате нам надо зайти во все столбцы(деревья по второй координате), находящиеся левее <tex>X</tex> и на одной горизонтальной линии с ним, и в каждом из них обновить все ячейки под <tex>Y</tex>(в рамках обозначений данного рисунка).]]
 Пусть имеем набор точек на плоскости с неотрицательными координатами. Определены 3 операции:
 # добавить точку в <tex>(x, y)</tex>;
@@ Строка 27: / Строка 27: @@
   '''int''' sum(x: '''int''', y: '''int'''):
          '''int''' result = 0
-         '''for''' ('''int''' i = x; i >= 0; i = (i & (i+1)) - 1)
+         '''for''' ('''int''' i = x; i >= 0; i = (i & (i + 1)) - 1)
-             '''for''' ('''int''' j = y; j >= 0; j = (j & (j+1)) - 1)
+             '''for''' ('''int''' j = y; j >= 0; j = (j & (j + 1)) - 1)
                 result += t[i][j];
          '''return''' result;
@@ Строка 34: / Строка 34: @@
 <code style = "display: inline-block;">
   '''func''' inc(x: '''int''', y: '''int''', delta: '''int'''):
-         '''for''' ('''int''' i = x; i < maxX; i = (i | (i+1)))
+         '''for''' ('''int''' i = x; i < maxX; i = (i | (i + 1)))
-             '''for''' ('''int''' j = y; j < maxY; j = (j | (j+1)))
+             '''for''' ('''int''' j = y; j < maxY; j = (j | (j + 1)))
                 t[i][j] += delta;
 </code>
@@ Строка 43: / Строка 42: @@
 [[Файл:ФормулаВключения-Исключения.jpg]]
-==Обобщение на большие размерности==
+====Обобщение на большие размерности====
-Чтобы увеличить размерность дерева Фенвика, нам достаточно во всех операциях для каждой новой размерности просто добавить вложенный цикл, пробегающий в ней соответствующие индексы.
+Дерево Фенвика относится к структурам данных, не требующим дополнительной памяти. В комбинации с простым представлением тривиального случая данной структуры это дает возможность легко повышать размерность дерева Фенвика, в котором в ячейках какого-то фиксированного уровня будет находиться дерево меньшей размерности. Для его реализации нам достаточно во всех операциях для каждой новой размерности просто добавить вложенный цикл, пробегающий в ней соответствующие индексы.
 ==См. также==
 *[http://e-maxx.ru/algo/fenwick_tree Дерево Фенвика]
 ==Источники информации==
-*[https://www.topcoder.com/community/data-science/data-science-tutorials/binary-indexed-trees/ Binary Indexed Trees]
+*[https://www.topcoder.com/community/data-science/data-science-tutorials/binary-indexed-trees/ Topcoder {{---}} Binary Indexed Trees]
 [[Категория: Дискретная математика и алгоритмы]]
-[[Категория: Структуры данных]]
+[[Категория: Модификации структур данных]]

← Предыдущая		Версия 18:16, 7 июня 2015
Строка 52:		Строка 52:

	[[Категория: Дискретная математика и алгоритмы]]		[[Категория: Дискретная математика и алгоритмы]]
−	~~[[Категория: Дерево Фенвика]]~~
	[[Категория: Структуры данных]]		[[Категория: Структуры данных]]

@@ Строка 1: / Строка 1: @@
 {{Определение
 |definition=
-'''Многомерное [[дерево Фенвика]]''' - структура данных, требующая <tex> O(n^k) </tex> памяти и позволяющая эффективно (за <tex> O(\log^k n) </tex>)
+'''Многомерное [[дерево Фенвика]]''' (англ. <i> Multidimensional Binary Indexed Tree</i>) {{---}} структура данных, требующая <tex> O(n^k) </tex> памяти и позволяющая эффективно (за <tex> O(\log^k n) </tex>)
 # изменять значение любого элемента в k-мерном массиве;
 # выполнять некоторую ассоциативную, коммутативную, обратимую операцию <tex> G </tex> на k-мерном прямоугольнике <tex> [i_1, \ldots ,i_k] </tex>;<br/> где n - максимальное значение для каждой координаты.
 }}
-Рассмотрим дерево Фенвика на примере k-мерного массива с k = 2, с увеличением k на единицу в операциях будет просто добавляться проход по k+1 измерению.
+Рассмотрим для начала дерево Фенвика на примере k-мерного массива с k = 2, а затем посмотрим, как можно обобщить его на большие размерности.
 Пусть дан массив <tex> A </tex> из <tex> n \times m </tex> элементов: <tex> a_{i,j}</tex>.<br/>
@@ Строка 17: / Строка 17: @@
 # посчитать количество точек в прямоугольнике <tex>(0, 0), (x, y)</tex>;
-<tex>n</tex> - количество точек, <tex>maxX</tex> - максимальная <tex>X</tex> координата, <tex>maxY</tex> - максимальная <tex>Y</tex> координата.<br/>
+<tex>n</tex> {{---}} количество точек, <tex>maxX</tex> {{---}} максимальная <tex>X</tex> координата, <tex>maxY</tex> {{---}} максимальная <tex>Y</tex> координата.<br/>
 Тогда дерево строится за <tex>O(n\cdot\log(maxX)\cdot\log(maxY))</tex>, а запросы выполняются за <tex>O(\log (maxX)\cdot\log (maxY))</tex>
-Добавляя точку вызовем <tex>inc(x, y, 1)</tex>, а удаляя <tex>inc(x, y, -1)</tex>. Таким образом запрос <tex>sum(x, y)</tex> дает количество точек в прямоугольнике.
+Добавляя точку вызовем <tex>\mathrm{inc}(x, y, 1)</tex>, а удаляя <tex>\mathrm{inc}(x, y, -1)</tex>. Таким образом запрос <tex>\mathrm{sum}(x, y)</tex> дает количество точек в прямоугольнике.
-''Пример реализации для двумерного случая:''
+==Псевдокод==
+t {{---}} массив, в котором хранится наше дерево Фенвика.
-<code>
+<code style = "display: inline-block;">
- vector <vector <int> > t;
+<font color=green>// </font>
- int n, m;
+  '''int''' sum(x: '''int''', y: '''int'''):
+         '''int''' result = 0
-  int sum (int x, int y)
+         '''for''' ('''int''' i = x; i >= 0; i = (i & (i+1)) - 1)
+            '''for''' ('''int''' j = y; j >= 0; j = (j & (j+1)) - 1)
-         int result = 0;
+               result += t[i][j];
-         for (int i = x; i >= 0; i = (i & (i+1)) - 1)
+         '''return''' result;
-           for (int j = y; j >= 0; j = (j & (j+1)) - 1)
+</code>
-              result += t[i][j];
+<code style = "display: inline-block;">
-         return result;
+  '''func''' inc(x: '''int''', y: '''int''', delta: '''int'''):
+         '''for''' ('''int''' i = x; i < maxX; i = (i | (i+1)))
+            '''for''' ('''int''' j = y; j < maxY; j = (j | (j+1)))
-  void inc (int x, int y, int delta)
+               t[i][j] += delta;
+  }
 </code>
-Чтобы посчитать значение функции для прямоугольника <tex>(x_1, y_1), (x_2, y_2)</tex> нужно воспользоваться формулой включения-исключения. Например для суммы: <tex>s = sum(x_2,y_2)-sum(x_2,y_1 - 1)-sum(x_1 - 1,y_2)+sum(x_1 - 1,y_1 - 1)</tex><br/>
+Чтобы посчитать значение функции для прямоугольника <tex>(x_1, y_1), (x_2, y_2)</tex> нужно воспользоваться формулой [[Формула включения-исключения|включения-исключения]]. Например, для суммы: <tex>s = \mathrm{sum}(x_2,y_2)-\mathrm{sum}(x_2,y_1 - 1)-\mathrm{sum}(x_1 - 1,y_2)+\mathrm{sum}(x_1 - 1,y_1 - 1)</tex><br/>
 [[Файл:ФормулаВключения-Исключения.jpg]]
-== Полезные ссылки: ==
+==Источники информации==
-Wikipedia: [http://en.wikipedia.org/wiki/Fenwick_tree Fenwick tree] <br/>
+*[https://www.topcoder.com/community/data-science/data-science-tutorials/binary-indexed-trees/ Binary Indexed Trees]