能否在O(n)时间内构建一棵Fenwick树？

Question

树状数组是一种数据结构，它允许两种操作(可以增加更多操作):

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

这两个操作的时间复杂度都为O(log(n)),其中n是数组的大小。我没有问题理解如何执行这两个操作以及它们背后的逻辑。

---

我的问题是如何从数组初始化树状数组。显然，我可以通过调用n次update(i,arr[i])来达到O(nlog(n))的时间复杂度，但是否有一种方式可以在O(n)的时间内进行初始化。

---

为什么会问这个问题，如果维基百科告诉你可以在nlog(n)内进行初始化?因为这篇文章太基础了，我不确定它是否是最优的复杂度。此外，将其与朴素堆创建进行对比，后者是通过一个一个地填充堆来完成的，可以在O(nlog(n))的时间内实现，而智能堆初始化则可以在O(n)的时间内完成，这让我希望可以在树状数组中实现类似的操作。

- Salvador Dali

---

跨站点重复：https://cs.stackexchange.com/questions/40540/why-isnt-the-time-complexity-of-constructing-a-fenwick-tree-tighter-than-on-l - David Eisenstat

@DavidEisenstat 没有重复，因为这里检查了一个 O(n*log(n)) 的算法，并提供了一个 O(n) 的算法。虽然很不错的发现。 - Vesper

@Vesper 这是一个O(n log n)时间复杂度的算法，经过仔细分析后被认为是O(n)。 - David Eisenstat

@DavidEisenstat 链接的问题更新显示，该算法实际上并不是朴素算法（在经验上似乎是Ω(n log n)），而是与我的非常相似 - 唯一的区别是它“pull”值而不是“push”它们。 - j_random_hacker

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这个算法是“新”的--虽然我没有仔细搜索过 ;)

- j_random_hacker

---

很印象深刻！虽然这会破坏原始数组，但总是可以将其复制到其他位置并处理副本。 - Vesper

非常有趣的方法！ - Sanket Makani

另外，我认为您忘记了x[i]+=array_element[i];在if条件语句之前。 - rushikesh chaskar

x[] 是起始数组 -- 该算法是原地算法，也就是说，它会将这个数组改造成一棵 Fenwick 树。 - j_random_hacker

哇！这太棒了，因为它不仅将构建时间降低到O(n)，而且将辅助空间复杂度降低到O(1)，因为它既不分配额外的空间，也不使用递归框架。 - nikojpapa

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 的帖子有相同的基本思路：我们更新当前节点和下一个更高级的父节点，利用所有子节点将始终在其各自的父节点之前被访问的属性。

- timg