Изменения

{{Определение|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>, а затем посмотрим, как можно обобщить его на большие размерности.

Добавляя точку вызовем <codetex>\mathrm{inc}(x, y, 1)</tex>, а удаляя <tex>\mathrm{inc}(x, y, -1)</tex>. Таким образом запрос <tex>\mathrm{sum}(x, y)</tex>дает количество точек в прямоугольнике.  vector [[Файл:example42.gif |thumb|600px|center|Пример дерева Фенвика <tex>(16 \times 8)</tex>. Синим обозначены элементы, которые обновятся при изменении ячейки <tex>(5, 3)</tex>. Чтобы обновить элемент <tex>(X, Y)</tex>, по первой координате нам надо зайти во все столбцы(деревья по второй координате), находящиеся левее <tex>X<vector /tex> и на одной горизонтальной линии с ним, и в каждом из них обновить все ячейки под <inttex> Y</tex> (в рамках обозначений данного рисунка).]] ==Псевдокод==<tex>\mathtt{t;}</tex> {{---}} массив, в котором хранится дерево Фенвика. 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; }