Всем привет, столкнулся с такой задачей: есть двумерное дерево Фенвика, нужно произвести модификацию на прямоугольнике. Хотелось самостоятельно обобщить модификацию обычного дерева Фенвика на отрезке на двумерный случай, но что-то нифига не получилось, готовых решений на этот счет тоже найти не удалось.
Соответственно, встали такие вопросы:
1) возможно ли такое вообще?
2) если да, пользуется ли кто-то этим или предпочитают альтернативы?
3) есть ли статьи/примеры/видео/что-либо на эту тему?
Ну сумма и прибавление к элементу на емаксе двумерное точно есть. Или нужен какой-то другой запрос?
Да нужно что-то типа такого, только на прямоугольнике :)
А чем это отличается от того, что я сказал? Возможно, я чего-то не понимаю.
http://e-maxx.ru/algo/fenwick_tree — там глава о двумерном случае, если что.
Ну как же, чем, в статье групповые модификации, а здесь единичные.
А, ну тогда нельзя наверно=)
Есть подозрения, что можно :) но моих фиолетовых мозгов чет не хватает, чтобы придумать, как это сделать :)
Да 146% можно. Может быть, к вечеру подумаю о том, как именно...
Примерно так же и делается. Только функцию надо хранить не совсем линейную, а вот такого вида: f(x, y) = ax + by + cxy + d.
Сначала превратили запросы на прямоугольниках в запросы на углах, растущих влево-вверх (формула включений-исключений). Говорим, что у нас запрос "сумма на угле" к двумерному Фенвику таких функций должен выдать некоторую функцию, подставив в которую координаты этого же угла должен получиться корректный ответ.
Запрос изменения на прямоугольнике аналогичны превратили в четыре запроса на углах, растущих вправо-вниз. Изменение каждого угла — это просто добавить в его вершину функцию вида f(x, y) = (x - x0 + 1)(y - y0 + 1).
спасибо за ответ! :) Но осмысление пока идет очень тяжело :))
Вот в этой работе что-то такое описывается.
Сам не разбирался, поэтому за достоверность не ручаюсь.
Дерево Фенвика с модификацией на отрезке
Варианты дерева Фенвика
спасибо! Однако, это то что нужно :)