Можно ли построить дерево Фенвика в O(n)?

Question

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

• обновление точки 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) дает мне надежду, что нечто подобное можно сделать в дереве Фенвика.

Answer 1

[РЕДАКТИРОВАТЬ: у меня были вещи "вверх ногами" - исправлено сейчас!]

Да. Перебирайте n элементов массива в порядке возрастания индекса, всегда добавляя сумму только к следующему наименьшему индексу, к которому она должна быть добавлена, а не ко всем из них:

for i = 1 to n:
    j = i + (i & -i)     # Finds next higher index that this value should contribute to
    if j <= n:
        x[j] += x[i]

Это работает, потому что, хотя каждое значение вносит вклад в несколько сумм диапазона, после обработки самой нижней суммы диапазона, в которую вносится значение (что фактически не требует "обработки", так как сумма уже существует), нам больше не нужно сохранять свою отдельную идентичность - его можно безопасно объединить со всеми другими значениями, которые вносят вклад в оставшиеся суммы диапазона.

ТТБОМК этот алгоритм "новый" - но тогда я не выглядел очень усердно;)

Answer 2

Вот реализация Java:

public BIT(long[] nums) {
        bit = new long[nums.length + 1]; //one-indexed
        for (int i = 1; i <= nums.length; i++) {
            bit[i] += nums[i - 1]; //update node
            if (i + (i & -i) <= nums.length) {
                bit[i + (i & -i)] += bit[i]; //update parent
            }
        }
    }

Та же общая идея, что и в сообщении j_random_hacker: мы обновляем текущий узел и следующий более высокий родительский узел, используя свойство, что все дочерние узлы всегда будут посещаться раньше, чем их соответствующие родительские узлы