Algorithmic Gems — Accumulation

Today I’d like to touch on a very simple yet powerful technique: Storing and manipulating data in cumulative form (aka prefix sum).

Imagine you are analyzing your company’s historical daily revenue, one way to store the data is using a one dimensional array with each cell storing the revenue amount for one day.

We can easily find the revenue for a specific day in constant time by looking up the value in the array cell for the day. However this storage scheme isn’t efficient when we start to deal with ranges, how can we calculate the total revenue for the last three months? Well, we have to iterate over every single day in the range, look up the revenue for that day and sum the numbers up, resulting in linear time complexity to answer range queries.

Whenever you find yourself dealing with ranges, think about storing data in cumulative form.

In our example here, we can store cumulative numbers: an array cell that corresponds to day i would store the total revenue the company made from day 1 to day i inclusive (also called prefix sum).

Now with the same space complexity you can answer range queries in constant time (improving on the linear time complexity above) by subtracting the cumulative revenue between the boundaries of range query.

Revenue from day i to day j = cumulative revenue at day j- cumulative revenue at day (i-1)

The idea of storing and manipulating data in cumulative form extends to more than one dimension.

For example if you have a two dimensional grid where each cell (i,j) stores the sum of values in cells between (1,1) and (i,j) then you can find the sum of any sub rectangle in the grid in constant time (Formula left as an exercise for the reader).

Storing data in cumulative form is not limited to cases when numbers are added together, depending on the problem at hand — other operators can work just as fine. One operator worth mentioning for being commonly used in prefix sums is the xor operator.

A very useful data structure built for manipulating prefix sums is Fenwick Tree (aka Binary Indexed Tree) which allows efficient read and write operations to the cumulative data structure. You can read more about Fenwick Tree here.

In conclusion, in your programs look for loops which accumulate consecutive elements and think about storing data in cumulative data structures and you might be able to neatly replace the loops with constant time operations.

You can read previous algorithmic gems here and follow our Facebook page to receive updates. As always I love to hear any feedback or questions.

Thanks for reading!