Fenwick树是一种数据结构，它允许两种操作（您可以通过更多操作来增强它）：
update(index, value)
query(index)
这两个操作都在数组的大小在O(log(n))哪里n。我不难理解如何进行操作及其背后的逻辑。
O(log(n))
n
我的问题是如何从数组初始化Fenwick树。显然我可以O(nlog(n))通过调用ntimes 实现它update(i, arr[i])，但是有一种方法可以初始化它O(n)。
O(nlog(n))
update(i, arr[i])
O(n)
为什么我问这个维基百科是否告诉您可以初始化nlog(n)？因为这篇文章太初级，所以我不确定这是否是可以实现的最佳复杂性。还通过天真的堆创建来绘制相似之处，该过程是通过逐个填充堆来完成的，并且O(nlog(n))与智能堆初始化相比可以实现O(n)，这给我希望可以在Fenwick树中完成类似的事情。
nlog(n)
[编辑：我的事情“倒置”-现在已解决！]
是。循环以递增的索引顺序遍历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这个算法是“新”的-但是后来我看起来并不难;）
