Изменения

'''Многомерное [[дерево Фенвика]]''' (англ. <i> Multidimensional Binary Indexed Tree</i>) {{- --}} структура данных, требующая <tex> O(n^k) </tex> памяти и позволяющая эффективно (за <tex> O(\log^k n) </tex>)

Рассмотрим для начала дерево Фенвика на примере k-мерного массива с k = 2, с увеличением k а затем посмотрим, как можно обобщить его на единицу в операциях будет просто добавляться проход по k+1 измерениюбольшие размерности.

<tex>n</tex> {{- --}} количество точек, <tex>maxX</tex> {{--- }} максимальная <tex>X</tex> координата, <tex>maxY</tex> {{--- }} максимальная <tex>Y</tex> координата.<br/>

Добавляя точку вызовем <tex>\mathrm{inc}(x, y, 1)</tex>, а удаляя <tex>\mathrm{inc}(x, y, -1)</tex>. Таким образом запрос <tex>\mathrm{sum}(x, y)</tex> дает количество точек в прямоугольнике.

''Пример реализации для двумерного случая:''==Псевдокод==t {{---}} массив, в котором хранится наше дерево Фенвика.<codestyle = "display: inline-block;"> vector <vector font color=green>// <int/font> > t; int n, m; '''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;

Чтобы посчитать значение функции для прямоугольника <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/>

== Полезные ссылки: Источники информации==Wikipedia: *[httphttps://enwww.wikipediatopcoder.orgcom/wikicommunity/Fenwick_tree Fenwick tree] <brdata-science/>edata-science-maxx.ru: [http:tutorials//ebinary-indexed-maxx.ru/algo/fenwick_tree Дерево Фенвика] <brtrees/>TopCoder: [http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees#find Binary Indexed Trees]