Prefix sums and difference arrays

Sales between any two times

A merchant dashboard is getting a new panel that shows the sales between any two times today, to the second. The first version keeps one sales total for each second of the day, 86,400 of them, and adds up the seconds in whatever range the merchant picks.

Work out the load before the load test runs. 500 merchants a second change their range. A whole-day range takes 86,400 additions, so the service needs about 43 million additions a second, and Python manages about 10 million. Requests pile up in a queue, and the panel takes longer to fill with every second the test runs.

Here are two numbers from the test data. By 10:00:00, ₹4,12,300 of sales had come in since midnight. By 14:00:00, the total since midnight was ₹9,87,650.

Pause and predict Using only those two running totals, how much came in between 10:00 and 14:00?

A range is a difference of two prefixes

Adding up a[l..r] directly costs one step per element. If you are asked for many ranges, you pay that cost again for every one.

Instead, do the work once. Walk through the array and write down the running totals: pre[i] is the sum of the first i values. Start with pre[0] = 0, the sum of no values at all, so pre has n + 1 entries.

Here is why. pre[r + 1] adds up a[0] to a[r], and pre[l] adds up a[0] to a[l - 1]. Both include a[0] to a[l - 1], so subtracting removes those values and leaves exactly a[l] to a[r]. So any range costs one subtraction. The table pre is called a prefix sum.

Pick a range, and the two prefix sums that give its total are highlighted:

The extra slot pre[0] lets one formula cover every range. A range that starts at index 0 is pre[r + 1] - pre[0], like every other range, so it needs no special case.

From range sums to counting subarrays

Now a harder question: how many subarrays sum to exactly k? An array of length n has about n²/2 subarrays, so checking each one is too slow.

Fix the right end r, and call the running total up to it P = pre[r + 1]. The subarray from l to r sums to P - pre[l].

Pause and predict For which earlier prefix sums pre[l] does the subarray from l to r add up to exactly k?

That is Two Sum from Unit 1, with prefix sums in place of values. Keep a map from each prefix sum to the number of times it has appeared. At each step, look up P - k in the map first, then add the current prefix sum P to it.

The order of the two steps matters, as it did in Unit 1. If you add P to the map before looking up P - k, then when k = 0 the lookup finds the P you just added. That match stands for an empty subarray with no elements, and it would be counted at every index.

Pause and predict Take [2, 3, -1] with k = 5, and suppose the map starts empty instead of holding the prefix sum 0. How many subarrays does the code count?

So the map starts as {0: 1}, holding pre[0], the sum of no values. It stands for the left end l = 0. If you leave it out, every subarray that starts at index 0 is lost. In [2, 3, -1] with k = 5, the only answer is [2, 3], and it is found through that starting entry: P = 5, and 5 - 5 = 0.

Why negatives do not matter

The per-second totals can be negative, when a refund in a quiet second is larger than the sales. Does that break anything?

The sliding window shrinks when the sum is too big. That relies on dropping an element lowering the sum and adding one raising it, and a negative value breaks both. Take [5, 3, -1] with k = 7. The window grows to [5, 3] with sum 8, which is too big, so it shrinks to [3]. Then it adds -1 and ends with sum 2. It never considers [5, 3, -1], which sums to 7.

The map never drops anything. At each step it answers an exact question, "how many times has P - k appeared?", and the answer does not depend on the signs of the values. So the choice between the two techniques comes down to this: use a window when the values are non-negative and you want the longest or shortest range, and use a prefix map when values can be negative or the sum must be exactly k.

The inverse: difference arrays

Prefix sums make reads cheap. Some problems need the reverse: many writes of the form "add v to every element of [l, r]", followed by one read of every value at the end.

The trick is to write down only where the values change. Keep an array d of n + 1 zeros. To add v to every element of [l, r], do d[l] += v and d[r + 1] -= v. After all the writes, a running sum of d gives every value. The array d is called a difference array.

Each write changes two cells, however long the range is, and the final read is one O(n) pass. This is the inverse of a prefix sum: if d[i] = a[i] - a[i - 1], then the prefix sums of d give back a. A difference array suits many cheap writes followed by one read, and a prefix sum suits one build followed by many cheap reads. d has n + 1 slots because a range that ends at the last index puts its -v one position past it.

Three more problems use these ideas without saying so:

How to recognise it

The words to listen for are "range", "subarray" and "exactly". The array either never changes, or all its changes come before a single read of the results.

Pause and predict The values can be negative, and you must count the subarrays that sum to exactly 7. Which technique fits?

Four that only look like it

• If the values are non-negative and you want the longest or shortest range under a limit, the sum only grows as the range grows, so a window does it in O(1) memory. That is sliding window.
• If you want a pair of values from anywhere in the array, keep a map of the values themselves. That is arrays and hashing.
• If updates and queries are mixed together, one update changes every later prefix sum, so rebuilding is too slow. That needs a Fenwick tree or a segment tree, covered in range queries.
• If intervals overlap and their coordinates are too large to index an array, use the same +1 and -1 idea, but sort the start and end events instead. That is intervals and sweep.

Where it bites

Pause and predict In Java, what does -7 % 3 evaluate to?

• Forgetting the starting entry. Without {0: 1} (or {0: -1} when you want the longest range), every subarray that starts at index 0 is missed.
• Mixing up inclusive and half-open ranges. pre[r] - pre[l] leaves out a[r]. In a difference array, a range that includes its end r puts -v at r + 1; Car Pooling's trips include from but not to, so the -v goes at to.
• Using a set where you need counts. Two equal prefix sums at different indices are two different left ends. A set records them once and loses one.
• Overwriting the first index in Contiguous Array. The map then holds the latest index of each prefix sum, so the ranges it finds are shorter than the longest.
• Using a sliding window when values can be negative. Check the signs of the values first.
• Forgetting to add the corner back in 2D. The top-left corner block was subtracted twice, so it must be added back once.