Дерево Фенвика это структура данных, которая допускает два вида операций (вы можете дополнить ее большим количеством операций):

обновление точкиupdate(index, value)сумма префиксаquery(index)

Обе операции находятся вO(log(n)) гдеn это размер массива. У меня нет проблем с пониманием того, как выполнять обе операции и их логику.

Мой вопрос заключается в том, как я могу инициализировать дерево Фенвика из массива. Очевидно, я могу достичь этого вO(nlog(n))по телефонуn разupdate(i, arr[i]), но есть ли способ инициализировать его вO(n).

Почему я спрашиваю это, если Википедия говорит, что вы можете инициализировать вnlog(n)? Поскольку статья настолько элементарна, что я не уверен, является ли это лучшей сложностью, которую можно достичь. Также проводим параллели с созданием наивной кучи, которая выполняется путем заполнения кучи одна за другой и может быть достигнута вO(nlog(n)) по сравнению с умной инициализации кучи вO(n) дает мне надежду, что нечто подобное можно сделать в дереве Фенвика.