是否可以在 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

[编辑：我有东西 "upside-down" -- 现在修复了！]

是的。以递增的索引顺序遍历 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]

这是可行的，因为虽然每个值都对几个范围总和有贡献，但在处理该值所贡献的最底部范围总和之后（实际上不需要 "processing"，因为总和已经在那里），我们没有不再需要保持其单独的身份——它可以安全地与所有其他有助于剩余范围总和的值合并。

TTBOMK 这个算法是 "new" -- 但后来我没仔细看 ;)

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 的 post 相同的总体思路：我们更新当前节点和下一个更高的父节点，使用之前总是访问所有子节点的属性他们各自的父节点

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

Is it possible to build a Fenwick tree in O(n)?

algorithm

fenwick-tree