在O(n)中构建Fenwick树是可能的吗？
在O(n)中构建Fenwick树是可能的吗？
提问于 2015-06-26 16:32:03
Fenwick tree是一种数据结构，它允许两种操作(你可以用更多的操作来扩充它)：
update(index, value)
- prefix sum
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树中完成类似的事情。
Stack Overflow用户
发布于 2020-10-19 13:41:14
下面是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的帖子的一般思想相同:我们更新当前节点和下一个更高的父节点，使用所有子节点总是在其各自的父节点之前被访问的属性
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/31068521
复制相关文章
相似问题
腾讯云开发者
