Prefix sums

Definition

The prefix sums of array a is such an array b that b[0] = 0, b[1] = a[0], b[2] = a[0] + a[1] and so on, b[n - 1] = a[0] + a[1] + ... + a[n - 2], and finally b[n] = a[0] + a[1] + ... + a[n - 1] that is, the sum of all the elements in the array.

It should be noted that the length of array b is one more than the length of array a.

In order to calculate the elements of the array b, we need O(n^2) time, which is not very efficient. Let's change our formula a little bit. Think about what formulas for b[i] and b[i + 1] have in common. Note that the formula for b[i + 1] is the same as the formula for b[i], but at the end, we just add more a[i]. So the sum of all terms except the last one can be replaced by b[i]. Thus, the formula for b[i + 1] can be simplified to b[i] + a[i].

Construction

Now, we can calculate the array of the prefix sums in O(n). Let's write a code that will calculate an array of prefix sums.

vector<int> mps(vector<int> &nums) {  // make prefix sum
  int n = nums.size();
  vector<int> prefixsum(n + 1, 0);

  for (int i = 0; i < n; i++)
    prefixsum[i + 1] = prefixsum[i] + nums[i];

  return prefixsum;
}

We accept as input the original array nums. Let's designate its size as n. Then we will create a final array prefixsum, which will have a length one more than a and fill it with zeros. Then we go through all the indexes of the array a and apply our recursive formula for each index i. And at the end, just return the final array.

Let's imagine that the elements of the original array are in cells. And the elements of the array of prefix sums are under the partitions between these cells. Their value is the sum of all the elements that are to the left of this very partition.

For example, there is nothing to the left of the zero partition. To the left of the divider of the five there is only a five, to the left of the divider of the eight there are five and three and so on.

Finding the sum on the segment in O(1)

Let us be given an array and some segment of this array. Question: what is the sum of the elements in this segment?

Let's build an array of prefix sums.

Note that the b[5] prefix sum contains all the element we need, but there are also extra ones. What are these superfluous? a[0] and a[1]. But the sum of these elements is exactly b[2]. That is, the sum of the array elements on the half-interval from 2 to 5 is just b[5] - b[2], so if we pre-calculated the array of prefix sums, then we can answer the request in O(1).

Let's summarize, there were numbers l and r, and we took the difference of the elements of the array b at these positions. The answer to problems like RSQ (Range Sum Query) is always b[r] - b[l].

Zero-sum segment

Let's solve one more problem, in which prefix sum will be used.
Let us be given an array, and we are required to find it's some non-empty subsegment with zero-sum of elements. For example, in this case, such a subsegment is suitable for us.

Note that the sum in the segment is equal to zero if and only if the prefix sums corresponding to its ends are equal to each other, because the sum in the segment is just the difference of the prefix sums.

To find such a pair, you can, for example, sort the array and search for identical pairs of adjacent elements. Alternatively, you can use a hash table, storing for each prefix sum the index of the prefix on which this sum is reached.

Number of zeros on the segment

Let us be given an array, and we need to find the number of zeroes on some non-empty subsegment. For example, in this case, the answer is 3.

For each prefix, we will count the number of zeros on it. Then the answer for the request on the half-interval is [l; r) will be b[r] - b[l].

Conclusion

We learned what prefix sums are and how they can be used to find a sum on a segment. Then we learned to find a subsegment of an array with a sum of zero. In the end, we learned how to use prefix sums to find the number of zeros (and not only) on a subsegment.