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

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

Многомерное дерево Фенвика - структура данных, требующая [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-мерного массива с k = 2, с увеличением k на единицу в операциях будет просто добавляться проход по k+1 измерению.

Пусть дан массив [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], как и в одномерном дереве Фенвика.

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

Пример дерева Фенвика [math](16 \times 8)[/math]. Синим обозначены ячейки, которые обновятся при изменении ячейки [math](5, 3)[/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]inc(x, y, 1)[/math], а удаляя [math]inc(x, y, -1)[/math]. Таким образом запрос [math]sum(x, y)[/math] дает количество точек в прямоугольнике.

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

vector <vector <int> > t;
int n, m;

int sum (int x, 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;
}

void inc (int x, int y, int delta)
{
       for (int i = x; i < n; i = (i | (i+1)))
          for (int j = y; j < m; j = (j | (j+1)))
             t[i][j] += delta;
}

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

Полезные ссылки:

Wikipedia: Fenwick tree
e-maxx.ru: Дерево Фенвика
TopCoder: Binary Indexed Trees