29

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

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

这两个操作都在O(log(n))wheren是数组的大小。我在理解如何进行操作及其背后的逻辑方面没有问题。

我的问题是如何从数组中初始化 Fenwick 树。O(nlog(n))显然，我可以通过调用ntimes来实现这一点update(i, arr[i])，但是有没有办法在O(n).

如果维基百科告诉你可以初始化，我为什么要问这个nlog(n)？因为这篇文章太简陋了，所以我不确定它是否是可以达到的最佳复杂性。还与天真的堆创建相似，这是通过一个一个地填充堆来完成的，并且可以在O(nlog(n))与智能堆初始化的对比中实现，O(n)这让我希望可以在 Fenwick 树中完成类似的事情。

4

2 回答 2

38

[编辑：我的东西“颠倒了”——现在修好了！]

是的。以递增的索引顺序循环遍历 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 这个算法是“新的”——但是我看起来不是很努力；）

于 2015-06-26T10:18:55.407 回答
0

这是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 的帖子相同的一般思想：我们更新当前节点和下一个更高的父节点，使用所有子节点将始终在其各自的父节点之前访问的属性

于 2020-10-19T05:41:13.523 回答