Start learning free

C++ · PARTIAL SUMS #1

Partial Sums Theory in C++, explained

What a partial sum is

A partial sum of an array is the sum of its first few elements. For an array arr, the partial sum at index i is arr[0] + arr[1] + ... + arr[i]. Computing it for every index gives a second array of running totals, often called a prefix sum array.

For arr = {1, 2, 3, 4, 5}, the partial sums are 1, 3, 6, 10, 15. Each one is the previous one plus the next element, so no sum is ever computed from scratch.

Building the array in C++

Keep a running total and write it into a second vector as you go. For {3, 1, 4, 1, 5} the totals are 3, 4, 8, 9 and 14:

vector<int> arr = {3, 1, 4, 1, 5};
vector<int> partial(arr.size());

int running = 0;
for (size_t i = 0; i < arr.size(); i++) {
    running += arr[i];
    partial[i] = running;
}
// partial: 3 4 8 9 14

The steps are always the same: start the total at 0, add each element, store the total. One pass does it, so the time is O(n) and the extra space is O(n) for the new vector.

The standard library has this ready as std::partial_sum in <numeric>. It reads a range and writes the running totals to an output iterator, and the output must have room for them:

vector<int> out(arr.size());
partial_sum(arr.begin(), arr.end(), out.begin());   // 3 4 8 9 14

The output range may be the input itself, which turns the vector into its own partial sums. C++17 adds inclusive_scan (same result) and exclusive_scan (each total leaves out the current element), and they can run in parallel.

Why they matter: sums of any range in O(1)

Partial sums pay off when you need many sums of ranges. Adding up arr[l] through arr[r] with a loop costs O(n) each time. If there are q such queries, that is O(n * q). With a prefix array built once, each query is one subtraction.

The layout that avoids special cases is a prefix array with one extra slot at the front: prefix[0] = 0 and prefix[i + 1] is the sum of the first i + 1 elements. Then the sum of arr[l..r] (both ends included) is prefix[r + 1] - prefix[l]:

vector<long long> buildPrefix(const vector<int>& arr) {
    vector<long long> prefix(arr.size() + 1, 0);
    for (size_t i = 0; i < arr.size(); i++) {
        prefix[i + 1] = prefix[i] + arr[i];
    }
    return prefix;
}

long long rangeSum(const vector<long long>& prefix, int l, int r) {
    return prefix[r + 1] - prefix[l];
}

On {3, 1, 4, 1, 5} the prefix array is 0 3 4 8 9 14. The sum of indexes 1 to 3 is prefix[4] - prefix[1] = 9 - 3 = 6, which is 1 + 4 + 1. The sum of the whole array is prefix[5] - prefix[0] = 14, and a single element works too: rangeSum(prefix, 2, 2) is prefix[3] - prefix[2] = 4. The leading 0 is what makes a range starting at index 0 work without an if.

The idea behind the subtraction: prefix[r + 1] counts everything up to r, prefix[l] counts everything before l, and the difference is exactly what lies between them. It also works with negative numbers, since it is plain subtraction: for {-2, 0, 3, -5, 2, -1}, the sum of indexes 2 to 5 is -1.

Common mistakes in C++

  • Off-by-one in the range formula. With the extra leading 0, use prefix[r + 1] - prefix[l]. Using prefix[r] - prefix[l] drops the last element. Without the extra slot, you need a special case for l == 0.
  • Overflow. Partial sums grow with every element. Three values of 2,000,000,000 sum to 6,000,000,000, which does not fit in an int (the largest is 2,147,483,647), and signed overflow is undefined behaviour. Store the totals in long long, as above. Note that partial_sum into a vector<int> overflows the same way.
  • Sizing the output wrongly. partial_sum writes through an iterator and does not resize anything. An output vector that is too small is a bug that may crash or silently corrupt memory.
  • Starting the total at the wrong value. The running total must begin at 0. Forgetting to set it gives a garbage start.
  • Using arr.size() - 1 on an empty vector. size() is unsigned, so arr.size() - 1 wraps to a huge number when the vector is empty. Loop with i < arr.size(). For an empty input, buildPrefix returns a vector with the single element 0.
  • Forgetting that the array is frozen. The prefix array is correct only for the array it was built from. If an element changes, every prefix after it is stale and needs rebuilding.

How you will use it in this chapter

The lessons that follow apply this idea to problems where recomputing a sum for every range would be too slow. The pattern is always the same: build the running totals in one pass, then answer each question with a subtraction. Looking at a problem, ask whether it repeatedly sums a range of an array, or compares the sum of one part with another. If so, a partial-sum array is likely to turn an O(n²) idea into an O(n) one.

Key takeaways

  • A partial (prefix) sum at index i is the sum of the elements from 0 to i. Build all of them in one pass with a running total.
  • Use prefix with one extra leading 0. Then the sum of arr[l..r] is prefix[r + 1] - prefix[l].
  • Building costs O(n) time and space, and every range query afterwards costs O(1).
  • std::partial_sum builds the totals in one call, but you must size the output and watch for int overflow.
  • Use long long for sums, and rebuild the array if the data changes.
Keep going with C++About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
Start learning free