Arrays and searching 0/120

Prefix sums · 1 of 3

Prefix sum technique

Store every prefix sum once, answer any range sum with one subtraction, and count subarrays by their sum with a map of prefix sums.

3,603 words · 17 min read

Part 1 of 8 Prefix sums

Many range sums on one array

Some problems give you an array once and then ask for the sums of many ranges of it, sometimes hundreds of thousands of them. A sliding window can keep a range's sum up to date when the range moves one step at a time, by adding the value that enters and subtracting the one that leaves. Here the ranges come in any order, so there is nothing to slide. Let's take a small array:

Each question names two positions and asks for the sum of the values from the first to the second, both included. The sum from position 1 to position 2 is 2+7=92 + 7 = 9, and the sum from position 0 to position 3 is 4+2+7+1=144 + 2 + 7 + 1 = 14. A loop that adds up the values of the range answers any one question, and for a single question it is all you need.

The loop is too slow when there are many questions. Say the array has nn values and there are qq questions. One question can cover the whole array, so it costs up to nn additions, and qq questions cost up to n×qn \times q. CSES Static Range Sum Queries, a contest version of this task, allows 200,000 values and 200,000 questions:

200,000×200,000=4×1010 additions200{,}000 \times 200{,}000 = 4 \times 10^{10} \text{ additions}

By the rule of thumb of about 10810^8 simple operations a second, that is 400 seconds of work against a one-second limit. Much of that work is repeated: the ranges overlap, and the loop adds the same values again for every question that covers them. To see how to avoid that, take the question about positions 1 to 2 again. Its answer is the sum of the first three values with the first value taken away:

(4+2+7)−4=13−4=9(4 + 2 + 7) - 4 = 13 - 4 = 9

A prefix sum is the sum of the first few values of an array: the first one, the first two, the first three, and so on. The sum of any range is one prefix sum minus a shorter one, so if we compute every prefix sum once and store them, each range sum takes a single subtraction, for a range of 2 values or of 200,000.