A few years ago, I learned certain algorithms that use "prefix sums" (also called cumulative sums) for calculating certain array operations in a faster way. For example, if your input array $arr[i]$ has $N$ elements, the prefix sum array $p[i]$ can be calculated using: $$ p[i] = \sum_{k=0}^{i} arr[k] $$ which can be computed fast by accumulating the elements from the original array. This then lets you compute the sum of any segment of the input array, using a simple subtraction: $$ \sum_{k=A}^{B} arr[k] = \sum_{k=0}^{B} arr[k] - \sum_{k=0}^{A-1} arr[k] = p[B]-p[A-1] $$
I noticed that you could calculate a "prefix sum" of the "prefix sum array": $$ q[i] = \sum_{k=0}^{i} p[k] = \sum_{k=0}^{i} \sum_{r=0}^{k} arr[r] $$ This "second-order" prefix sum (not sure if there's a better name) can then be used to calculate other more complex combinations of the input array. For example,
$$ \sum_{k=0}^{i} (i-k)\cdot arr[k] = q[i]-p[i] $$
In this case, instead of adding many elements of the input array, we can just subtract two elements of the prefix sums arrays (as we only compute the prefix sums once, each query would be O(1) instead of O(N)). Of course, this is a simple example, but I guess that calculating even higher order prefix sums could be more powerful for other types of calculations.
The first idea that came to my mind is that this could be used to perform fast arbitrary triangular filter banks (such as the one used for extracting MFCC coefficients from a signal, see this question as an example), but maybe there are more applications.
My questions are:
- Are repeated/higher-order prefix sums being used anywhere? I tried searching for some papers but couldn't find them.
- Can you decompose any linear combination of elements of the input array into a linear combination of elements of any of the Nth prefix sums (presumably one that uses as fewer terms as possible)?
- How can you (efficiently) know which combination of elements of the prefix sums yield a given linear combination of the original inputs?
- Is there any way to implement this without running into precision loss? I guess that using integers would better because they can overflow and when doing operations they don't lose the "important parts" (lower bits), but if I were to implement this with huge input numbers, making a linear combination of the prefix sums would yield incorrect results, due to the accumulation of errors.