是否可以在O(n)中构建Fenwick树？

Question

Fenwick树是一种允许两种操作的数据结构(您可以通过更多操作来扩充它):

• 点更新 update(index, value)
• 前缀总和 query(index)

两个操作都是在O(log(n))其中n是一个数组的大小.理解如何进行操作及其背后的逻辑,我没有任何问题.

---

我的问题是如何从数组初始化Fenwick树.很明显,我可以O(nlog(n))通过调用n时间来实现这一点update(i, arr[i]),但有没有办法将其初始化O(n).

---

如果维基百科告诉您可以初始化,我为什么要问这个nlog(n)？因为这篇文章是如此简陋,我不确定它是否是人们能够实现的最佳复杂性.还可以通过逐个填充堆来完成与初始堆创建的相似之处,并且可以在O(nlog(n))智能堆初始化中实现O(n),这使我希望在Fenwick树中可以完成类似的操作.

Answer 1

[编辑:我把事情"颠倒" - 现在修复!]

是.以递增的索引顺序循环遍历n个数组项,始终只将sum 加到应该添加到的下一个最小索引,而不是全部:

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]

这是有效的,因为虽然每个值都有助于多个范围和,但在处理了值所贡献的最低范围和之后(实际上不需要"处理",因为总和已经在那里),我们不再需要保持其单独的身份 - 它可以安全地与所有其他有助于剩余范围总和的值合并.

TTBOMK这个算法是"新的" - 但后来我看起来并不是很努力;)