Я занимаюсь оптимизацией в одном проекте, который сильно не укладывается в требования по производительности. Тут широко используются деревья Фенвика для быстрого получения префиксных сумм (AKA промежуточные суммы) для массива с постоянно изменяющимся содержимым. Сама по себе структура очень полезная и сильно выручает, но здесь кроме стандартных операций инкремента произвольных элементов очень часто используются две дополнительные нестандартные операции (я не нашел аналогов в литературе). И на эти операции приходится значительная часть вычислительной нагрузки.
Получение значений (выгрузка во внешний массив) префиксных сумм для элементов из непрерывного диапазона от
i
доi + k
.Обнуление (или, скажем, заполнение константой) элементов из непрерывного диапазона от
i
доi + k
с корректным пересчетом всех затрагиваемых сумм.
Важно: Для обоих операций среднее значение k
много меньше n
(количества элементов в дереве).
На данный момент реализованы эти операции тупо и просто:
В цикле (отдельно!) для каждого элемента из диапазона выполняется нахождение его значения (стандартная операция для дерева Фенвика). Итого: сложность операции составляет
O(k*log(n))
дляk
элементов.В цикле (отдельно!) для каждого элемента выполняется нахождение его значения, после чего выполняется его инкремент на число обратное его текущему значению (для сброса в ноль). Сложность, опять же, равна
O(k*log(n))
.
Я задумался над структурой деревьев и этими операциями. И мне кажется, обе они могут быть реализованы с меньшей сложностью. Ведь log(n)
это глубина прохода от корня до произвольного элемента, а в этих операциях выполняется обход группы последовательно расположенных элементов. Из этого факта возможно извлечь пользу, так как ближайший общий узел дерева в лучшем случае лежит на глубине log(k)
от любого из конечных узлов в непрерывном диапазоне длинной k
. Значит для обхода всего диапазона можно спуститься от корня за log(n)
, после чего подниматься и спускаться от одного соседнего элемента к другому за log(k)
. Итого: сложность алгоритма должна составить O(log(n) + k*log(k))
(что намного лучше текущего варианта). Это для лучшего случая. Но и средняя оценка должна быть близка к этому, так как худший случай O(k*log(n))
маловероятен при k ≪ n
.
Сейчас я залип над реализаций алгоритмов для этих двух операций. Пока что мне не совсем понятно как перейти от элемента i
к элементу i+1
, не возвращаясь к корню. По идее надо подниматься до ближайшего общего узла и спускаться обратно к следующему элементу, по дороге подсчитывая суммы, необходимые для получения значения следующего элемента. А для операции (2), видимо, следует на этом же проходе одновременно корректировать значения промежуточных узлов как при выполнении стандартного инкремента (если это вообще возможно сделать одновременно).
Это все общие соображения для бинарных деревьев. Как это должно реализовываться конкретно для дерева Фенвика я пока не представляю.
Буду благодарен за помощь с конкретными алгоритмами на псевдокоде или любом императивном языке.
Если мои рассуждения на счет сложности неверны, то хотелось бы узнать в чем конкретно я ошибаюсь.