Многомерное дерево Фенвика

Определение:

Многомерное дерево Фенвика (англ. Multidimensional Binary Indexed Tree) — структура данных, требующая [math] O(n^k) [/math] памяти и позволяющая эффективно (за [math] O(\log^k n) [/math]) изменять значение любого элемента в k-мерном массиве; выполнять некоторую ассоциативную, коммутативную, обратимую операцию [math] G [/math] на k-мерном прямоугольнике [math] [i_1, \ldots ,i_k] [/math]; где n - максимальное значение для каждой координаты.

Рассмотрим для начала дерево Фенвика на примере k-мерного массива с [math]k = 2[/math], а затем посмотрим, как можно обобщить его на большие размерности.

Пусть дан массив [math] A [/math] из [math] n \times m [/math] элементов: [math] a_{i,j}[/math].
Деревом Фенвика будем называть массив [math] T [/math] из [math] n \times m [/math] элементов: [math] T_{i,j} = \sum\limits_{k = F(i)}^{i} \sum\limits_{q = F(j)}^{j}a_{k,q}[/math], где [math]F(i) = i\; \&\; (i + 1)[/math], как и в одномерном дереве Фенвика.

Пример задачи для двумерного случая

Пусть имеем набор точек на плоскости с неотрицательными координатами. Определены 3 операции:

1. добавить точку в [math](x, y)[/math];
2. удалить точку из [math](x, y)[/math];
3. посчитать количество точек в прямоугольнике [math](0, 0), (x, y)[/math];

[math]n[/math] — количество точек, [math]maxX[/math] — максимальная [math]X[/math] координата, [math]maxY[/math] — максимальная [math]Y[/math] координата.
Тогда дерево строится за [math]O(n\cdot\log(maxX)\cdot\log(maxY))[/math], а запросы выполняются за [math]O(\log (maxX)\cdot\log (maxY))[/math]

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

Пример дерева Фенвика [math](16 \times 8)[/math]. Синим обозначены элементы, которые обновятся при изменении ячейки [math](5, 3)[/math]. Чтобы обновить элемент [math](X, Y)[/math], по первой координате нам надо зайти во все столбцы(деревья по второй координате), находящиеся левее [math]X[/math] и на одной горизонтальной линии с ним, и в каждом из них обновить все ячейки под [math]Y[/math](в рамках обозначений данного рисунка).

Псевдокод

[math]\mathtt{t}[/math] — массив, в котором хранится дерево Фенвика.

int sum(x: int, y: int):
       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;

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)))
              t[i][j] += delta;

Чтобы посчитать значение функции для прямоугольника [math](x_1, y_1), (x_2, y_2)[/math] нужно воспользоваться формулой включения-исключения. Например, для суммы: [math]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)[/math]

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

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

Источники информации

• Topcoder — Binary Indexed Trees
• Дерево Фенвика