在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树中完成类似的事情。
回答 2
Stack Overflow用户
回答已采纳
发布于 2015-06-26 18:18:55
编辑:我把东西“颠倒了”--现在修复了！
是。按索引递增顺序遍历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这个算法是“新的”--但是我还没仔细研究过;)
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
复制相关文章
相似问题
腾讯云开发者
