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

29
votes

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.

2
algorithmfenwick-tree
Cross-site duplicate: cs.stackexchange.com/questions/40540/… – David Eisenstat
@DavidEisenstat No duplicate, since there an algorithm of O(n*log(n)) is checked, and here an O(n) algorithm is requested and provided. Although nice find. – Vesper
@Vesper It's an O(n log n)-time algorithm that is more carefully analyzed to be O(n). – David Eisenstat
An update on the question @DavidEisenstat linked to reveals that the algorithm in question there isn't the naive algorithm after all (which empirically does seem to be Omega(n log n)), but one that actually is very similar to mine -- the only difference being that it "pulls" values instead of "pushing" them. – j_random_hacker

2 Answers

37
votes

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

0
votes

Here's the Java implementation:

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
            }
        }
    }

Same general idea as j_random_hacker's post: we update the current node and the next higher parent node, using the property that all children nodes will always be visited before their respective parent nodes