Как сделать 2D-дерево Фенвика для суммы в прямоугольнике и за сколько это работает?
Нужна сумма на подматрице [(x1,y1)..(x2,y2)] с точечными обновлениями клеток. Понимаю одномерный BIT, но как обобщить на два измерения и какая будет сложность по времени и памяти? Сетка до 1000×1000.
2 ответа
2D BIT — это «Фенвик из Фенвиков»: оба индекса бегают по своим младшим битам. Точечное обновление трогает блоки в обоих измерениях, префиксный запрос — сумму прямоугольника [1..x][1..y].
struct BIT2D {
int n, m; vector<vector<long long>> t;
BIT2D(int n, int m): n(n), m(m), t(n+1, vector<long long>(m+1, 0)) {}
void update(int x, int y, long long v){
for (int i = x; i <= n; i += i & -i)
for (int j = y; j <= m; j += j & -j)
t[i][j] += v;
}
long long query(int x, int y){ // сумма [1..x][1..y]
long long s = 0;
for (int i = x; i > 0; i -= i & -i)
for (int j = y; j > 0; j -= j & -j)
s += t[i][j];
return s;
}
long long rect(int x1, int y1, int x2, int y2){ // включ. границы
return query(x2,y2) - query(x1-1,y2)
- query(x2,y1-1) + query(x1-1,y1-1);
}
};
Сумма прямоугольника — формула включений-исключений из четырёх префиксов. Сложность: update/query — O(log n · log m), rect — те же четыре запроса, тоже O(log n · log m). Память — O(n·m) (для 1000×1000 это ~8 МБ при long long, нормально). Аккуратно с границами x1-1/y1-1 — при x1=1 или y1=1 префикс корректно даст 0.
Если сетка большая по координатам, но точек мало (разреженный случай), плотный 2D BIT по памяти не влезет (10^9 клеток). Тогда либо офлайн со сжатием координат по второй оси (BIT из отсортированных списков), либо BIT с unordered_map во внутреннем измерении — но это медленнее и по константе тяжелее. Для плотной сетки ≤ 2000×2000 хватает обычного 2D-массива, как выше. Ещё: range-update в 2D Фенвике делается, но формула с четырьмя BIT громоздкая — если нужно и обновление прямоугольника, и запрос прямоугольника, прикиньте, не проще ли 2D segment tree / другой подход.