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

Question

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

• 点更新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 个数组项，总是将总和仅添加到它应该添加到的下一个最小索引，而不是添加到所有索引:

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 这个算法是"new"的——但我并没有仔细研究 ;)