Calculating sub array sums with a Fenwick tree

Question

I have a problem and I don't know if I can solve it with a Fenwick tree. Here's the problem: I have an original array a = [8,4,7,0]. Now I iterate through the array and at each step I am interested in the sorted sub-arrays, which look like this: [8], [4,8], [4,7,8], [0,4,7,8]. At each step of the iteration when I insert the current number, I want to know the sum of all numbers that are bigger than the one I just inserted. So for the above example it would look like this:

[8]; sum = 0 since the sum of all numbers bigger than the inserted number (8) is 0
[4,8]; sum = 8 since the sum of all numbers bigger than the inserted number (4) is 8
[4,7,8]; sum = 8 since the sum of all numbers bigger than the inserted number (7) is 8
[0,4,7,8]; sum = 19 since the sum of all numbers bigger than the inserted number (0) is 19

The above example is just for illustration and the original array can be much larger so that calculating such sums efficiently becomes very important. Any suggestion on how I can solve this efficiently?

score 2 · Accepted Answer · answered Feb 01 '21 at 17:50

Assuming you know the array offline, you can sort to find the rank of each element, e.g., [8, 4, 7, 0] --> [(8, 3), (4, 1), (7, 2), (0, 0)]. Then initialize a Fenwick tree with all zeros, and to process an element, sum the suffix of the Fenwick tree corresponding to higher ranks and then insert the element at its rank. The evolution of the Fenwick tree is

[0, 0, 0, 0]
          --: sum = 0

[0, 0, 0, 8]
    --------: sum = 8

[0, 4, 0, 8]
       -----: sum = 8

[0, 4, 7, 8]
 -----------: sum = 19

If you need to run online then I think it's easiest to augment a balanced binary search tree.

Calculating sub array sums with a Fenwick tree

1 Answers1