1632
правки
Изменения
м
[[Файл:example42.gif |thumb|600px|right|Пример дерева Фенвика <tex>(16 \times 8)</tex>. Синим обозначены ячейки, которые обновятся при изменении ячейки <tex>(5, 3)</tex>]]
''[[Файл:example42.gif |thumb|600px|center|Пример реализации для двумерного случая:''дерева Фенвика <tex>(16 \times 8)</tex>. Синим обозначены элементы, которые обновятся при изменении ячейки <tex>(5, 3)</tex>. Чтобы обновить элемент <tex>(X, Y)</tex>, по первой координате нам надо зайти во все столбцы(деревья по второй координате), находящиеся левее <tex>X</tex> и на одной горизонтальной линии с ним, и в каждом из них обновить все ячейки под <tex>Y</tex>(в рамках обозначений данного рисунка).]]
== Полезные ссылки: ==Wikipedia: [http[Категория://en.wikipedia.org/wiki/Fenwick_tree Fenwick treeДискретная математика и алгоритмы]] <br/>e-maxx.ru: [http[Категория://e-maxx.ru/algo/fenwick_tree Дерево ФенвикаМодификации структур данных] <br/>TopCoder: [http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees#find Binary Indexed Trees]
rollbackEdits.php mass rollback
{{Определение
|definition=
'''Многомерное [[дерево Фенвика]]''' (англ. <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-мерного массива с <tex>k = 2</tex>, с увеличением k а затем посмотрим, как можно обобщить его на единицу в операциях будет просто добавляться проход по k+1 измерениюбольшие размерности.
Пусть дан массив <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>, как и в одномерном [[дерево Фенвика|дереве Фенвика]].
==Пример задачи для двумерного случая==
Пусть имеем набор точек на плоскости с неотрицательными координатами. Определены 3 операции:
# добавить точку в <tex>(x, y)</tex>;
# посчитать количество точек в прямоугольнике <tex>(0, 0), (x, y)</tex>;
<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>\mathrm{inc}(x, y, 1)</tex>, а удаляя <tex>\mathrm{inc}(x, y, -1)</tex>. Таким образом запрос <tex>\mathrm{sum}(x, y)</tex> дает количество точек в прямоугольнике.
==Псевдокод==<codetex> vector <vector \mathtt{t}<int/tex> > t;{{---}} массив, в котором хранится дерево Фенвика. int n, m<code style = "display: inline-block;"> '''int ''' sum (x: '''int x''', y: '''int y''') {: '''int ''' result = 0; '''for ''' ('''int ''' i = x; i >= 0; i = (i & (i+1)) - 1) '''for ''' ('''int ''' j = y; j >= 0; j = (j & (j+1)) - 1) result += t[i][j]; '''return ''' result; }</code> <code style = "display: inline-block;"> void '''func''' inc (x: '''int x''', y: '''int y''', delta: '''int delta''') {: '''for ''' ('''int ''' i = x; i < nmaxX; i = (i | (i+1))) '''for ''' ('''int ''' j = y; j < mmaxY; j = (j | (j+1))) t[i][j] += delta; }
</code>
Чтобы посчитать значение функции для прямоугольника <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]]
====Обобщение на большие размерности====
Дерево Фенвика относится к структурам данных, требующим малое количество дополнительной памяти. В комбинации с простым представлением тривиального случая данной структуры это дает возможность легко повышать размерность дерева Фенвика, в котором в ячейках какого-то фиксированного уровня будет находиться дерево меньшей размерности. Для его реализации нам достаточно во всех операциях для каждой новой размерности просто добавить вложенный цикл, пробегающий в ней соответствующие индексы.
==См. также==
* [[Дерево Фенвика]]
* [[Встречное дерево Фенвика]]
* [[Дерево Фенвика для некоммутативных операций]]
==Источники информации==
*[https://www.topcoder.com/community/data-science/data-science-tutorials/binary-indexed-trees/ Topcoder {{---}} Binary Indexed Trees]
*[http://e-maxx.ru/algo/fenwick_tree Дерево Фенвика]
