是否可以在O（n）中构建Fenwick树？ [英] Is it possible to build a Fenwick tree in O(n)?

问题描述

Fenwick树是一种数据结构，它允许两种操作（您可以使用更多操作）：

• 点更新 update（索引，值）


• 前缀总和 query（index）

这两个操作都在 O（log（n））中，其中 n 是数组的大小。我完全理解如何进行操作及其背后的逻辑。

---

我的问题是如何初始化一个数组的Fenwick树。显然，我可以通过调用 n 次在 O（nlog（n））中实现这一目标update（i，arr [i]），但是有一种方法可以在 O（n）中对其进行初始化。

---

我为什么要问维基百科是否告诉您可以在 nlog（n）中初始化？因为这篇文章太基本了，所以我不确定这是否是可以实现的最佳复杂性。还可以通过天真地创建一个堆来绘制天真的堆，这是通过一个一个地填充堆来完成的，可以在 O（nlog（n））中实现，而在<$ c中进行智能堆初始化$ c> O（n）让我希望可以在Fenwick树中完成类似的事情。

解决方案

是的。循环以递增的索引顺序遍历n个数组项，始终将总和 only 添加到应该添加到的下一个最小索引中，而不是全部添加到其中：

对于i = 1至n：

 ：
j = i +（i& -i）＃查找该值应有助于$ b的下一个更高的索引如果j< = n：
x [j] + = x [i] 
  

之所以起作用，是因为尽管每个值都贡献了多个范围总和，但在处理了该值所贡献的最底范围总和之后（由于总和已经存在，因此实际上不需要处理），我们不再需要将其分开身份-它可以安全地与所有有助于剩余范围总和的值合并。看起来很辛苦；）

Fenwick tree is a data structure which allows two kind of operations (you can augment it with more operations):

• point update update(index, value)
• prefix sum query(index)

Both of the operations are in O(log(n)) where n is the size of an array. I have no problems understanding how to do both operations and the logic behind them.

---

My question is how can I initialize a Fenwick tree from an array. Clearly I can achieve this in O(nlog(n)), by calling n times update(i, arr[i]), but is there a way to initialize it in O(n).

---

Why am I asking this if wikipedia tells that you can initialize in nlog(n)? Because the article is so rudimentary, that I am not sure whether it is the best complexity one can achieve. Also drawing parallels with naive heap creation which is done by populating the heap one by one and can be achieved in O(nlog(n)) versus smart heap initialization in O(n) gives me hope that something similar can be done in Fenwick tree.

解决方案

[EDIT: I had things "upside-down" -- fixed now!]

Yes. Loop through the n array items in increasing index order, always adding the sum only to the next smallest index that it should be added to, instead of to all of them:

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]

This works because although every value contributes to several range sums, after processing the bottommost range sum that the value contributes to (which actually requires no "processing", since the sum is already in there), we no longer need to maintain its separate identity -- it can safely be merged with all other values that contribute to the remaining range sums.

TTBOMK this algorithm is "new" -- but then I haven't looked very hard ;)

这篇关于是否可以在O（n）中构建Fenwick树？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！