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

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

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

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

Пример дерева Фенвика [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];

m - количество точек, maxX - максимальная x координата, maxY - максимальная y координата. тогда дерево строится за [math]O(m\log (maxX)\,\log (maxY))[/math], а запросы выполняются за [math]O(\log (maxX)\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