Многомерное дерево Фенвика
Версия от 07:27, 10 мая 2011; 192.168.0.2 (обсуждение)
Дерево Фенвика легко обобщается на многомерный случай.
Пример реализации для двумерного случая:
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; }
Пример дерева Фенвика . Синим обозначены ячейки, которые обновятся при изменении ячейки
Полезные ссылки:
Wikipedia: Fenwick tree
e-maxx.ru: Дерево Фенвика
TopCoder: [1]