Is it possible to build a Fenwick tree in O(n)?

Question

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.

Answer 1

[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 ;)