Prefix sum

Written by Benjamin Schmid. Translated by Benjamin Schmid.

In this article we will have a look at prefix sums. We will start with the one dimensional case and expand later to two dimensions. This trick is easy to use but can be used as a powerful building block for many problems.

Problem

What kind of problems can be solved with a prefix sum? We are given a table of numbers and we have to calculate the sum in a part of the table very often. Or in other words: Given an $$M\times N$$ rectangle with numbers. Calculate the sum of all numbers for $$Q$$ different subrectangles.

Let’s first have a look at the one dimensional case where we have a list with $$N$$ numbers. The first approach is to sum up all numbers for the queried range. Something similar to this:

for segment in segments: # Q Queries
sum = 0
for i in range(segment.start, segment.end):
sum += list_of_numbers[i]
print(sum)

This is too slow if we have many queries because each of the $$Q$$ queries takes up to $$N$$ operations. The algorithm runs in $$\mathcal{O}(N\cdot Q)$$

Solution

The trick is do more work at the beginning and precalculate some values. With those additional informations we can answer the queries faster. Instead of summing up all numbers in $$\mathcal{O}(N)$$ for each query we can then calculate it in $$\mathcal{O}(1)$$. Let’s find out how this works.

The list $$A$$ with the elements $$a_1$$, $$a_2$$, $$a_3$$, …, $$a_N$$ contains the numbers given in the input. To calculate the sum in the range $$x$$ to $$y$$ we can sum up all numbers from the beginning up to $$y$$ and then subtract the numbers from the beginning to $$x-1$$. If we have several ranges all ending at $$y$$ the first sum (from the beginning to $$y$$) will not change. Only the ones we subtract (beginning to $$x-1$$) will change. Something similar holds if $$x$$ is not changed but only $$y$$. This looks very good to precalculate something!

We will precalculate a list $$B$$ such that $$b_i$$ corresponds to the sum of all numbers of the list $$A$$ from the beginning up to and including $$i$$. Now we can use the proposed algorithm: the sum in the range $$x$$ to $$y$$ is exactly $$b_y - b_{x-1}$$. Why does this work?

Let’s look for example at the range $$3 - 6$$. The sum we want to calculate is $$a_3 + a_4 + a_5 + a_6$$. Then we have $$b_6 = a_1 + a_2 + a_3 + a_4 + a_5 + a_6$$ and $$b_2 = a_1 + a_2$$. If we compute $$b_6 - b_2$$ we get $$b_6 - b_2 =$$ $$(a_1 + a_2 + a_3 + a_4 + a_5 + a_6) - (a_1 + a_2) =$$ $$(a_1 - a_1) + (a_2 - a_2) + a_3 + a_4 + a_5 + a_6 =$$ $$a_3 + a_4 + a_5 + a_6$$. This is exactly the sum we are looking for. We can remove the elements we added “too much” by subtracting $$b_2$$. This can be implemented like this:

# precalculation
b =  * len(a)
b = a
for i in range(1, len(a)):
b[i] = b[i-1] + a[i]

# queries
for segment in segments:
if segment.start == 0:
print(b[segment.end])
else:
print(b[segment.end] - b[segment.start-1])

The precalculation can be done in $$\mathcal{O}(N)$$ and all queries in $$\mathcal{O}(Q)$$ (as we can do one query in constant time). We improved the original solution from $$\mathcal{O}(N\cdot Q)$$ to $$\mathcal{O}(N+Q)$$

Solution for two dimensions

We can extend this trick to two dimensions. Let $$A$$ be the given rectangle and $$B$$ the precalculated rectangle. Which values do we need in $$B$$ to be able to calculate the sum of subrectangles efficiently? As we can see in the image above the yellow rectangle can be calculated with the four other rectangles (they represent the sum of the covered fields). Those four rectangles have their upper left corner in the upper left corner of $$A$$. This is exactly the same as in the one dimensioal case where all ranges touched the left end.

In $$B$$ we calculate in each field the sum of the subrectangle from the upper left corner to the current field. This can be done efficiently with several approaches. One possibility is to walk through the rectangle row by row from left to right and set $$b_{y,x} = b_{y-1,x} + b_{y,x-1} - b_{y-1,x-1} + a_{y,x}$$. The subtraction is necessary as we would count this subrectangle twice otherwise.

We can now calculate the sum of a subrectangle from $$(i_x|i_y)$$ to $$(j_x|j_y)$$ with the formula $$b_{j_y,j_x} - b_{i_y-1,j_x} - b_{j_y,i_x-1} + b_{i_y-1,i_x-1}$$. As in the one dimensional case we take a range too big (going to $$(j_x|j_y)$$) and then subtract the things we added too much (the left and upper rectangle). Unfortunately we subtracted the range to $$(i_x-1|i_y-1)$$ twice so we have to add it again. Note that we used different formulas for precalculation and queries.

The algorithm can be implemented as follows:

# precalculation
b = [ * (width + 1)] * (height + 1)
for y in range(1, height):
for x in range(1, width):
b[y][x] = b[y-1][x] + b[y][x-1] - b[y-1][x-1] + a[y-1][x-1]

# queries
for segment in segments:
print(b[segment.y2][segment.x2]
- b[segment.y1][segment.x2]
- b[segment.y2][segment.x1]
+ b[segment.y1][segment.x1])