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

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