Understanding prefix sums

Everyone knows what a prefix is

Prefix comes from the latin word praefixus, meaning “fixed in front”. In computer science, we treat prefixes as some elements preceding other elements in a sequence. For most introductory computer science courses, you will be introduced to the Knuth-Morris-Pratt (KMP) algorithm for string matching, which uses the same idea of prefixes. In this post, I aim to introduce a easier application of prefix algorithms/techniques.

Why do we use prefixes?

Prefixes save us loads of computation by precomputing differences. At the cost of (maybe) some linear memory complexity, we save orders of magnitude on time complexity. We can think of this as having almost like a look-up table for things we want to calculate. This especially saves time on repeated calculations like partial sums and substring comparisons.

The problem that helped me understand

Let’s take a look at CF 1807D - Odd Divisor.
We are given some the length of an array and some number of scenarios, followed by the array of integers, okay easy enough.

For each array of integers, we are presented with a number of tasks consisting of two indexes, l and r, and some value k.

The problem we are to solve is wether or not replacing all values between the two indexes (inclusive) with the value k will make the sum of all elements in the array odd.

It’s important to note that each task is to be completed independently, so none of them should change the value of anything in the array

Those last two sentences are a bit of a mouthful, so let’s take a look at some of the testcases given.
The array given is {2, 2, 1, 3, 2}.
An example task is given as {1, 5, 5}, so we would set everything between elements 1 and 5 to 5. This gives us a new array {5, 5, 5, 5, 5}. The sum of this array is 25, so print “YES” because it is odd.

The naive solution

Let’s use the following properties of modular arithmetic:

  • odd - even = odd
  • even - even = even
  • odd - odd = even
  • even - odd = odd

We can reduce the previous problem to just finding the sum of the array between indexes l and r, then subtracting k * (r - l + 1) from it and taking the difference between that and the sum of the original array. So we have the formula:

  • original_array_sum - difference = ???

by taking modulo 2 of the left side, we arrive at our answer

where original_array_sum is the original sum of all array elements
and difference is sum(array[l], … , array[r]) - k * (r - l + 1).

from here it’s trivial to find sum(array[l], …, array[r]) with one for loop, and the calculation for k * (r - l + 1) is easy.

We end up with a runtime complexity of O(n + q*(r - l))

Using an algorithm like the following:

#include <iostream>
#include <cstring>

void solve() {
    int n; int q;
    std::cin >> n >> q;
    int cnt{};
    bool arr[n];
    memset(arr, 0, sizeof(arr));
    for(int i = 0; i < n; i++){
        int buffer;
        std::cin >> buffer;
        arr[i] += buffer % 2;
        cnt += buffer %2;
    }
    cnt %= 2;
    for(int i = 0; i < q; i++){
        int l, r, k;
        std::cin >> l >> r >> k;
        int delta = (r - l + 1)% 2 * (k) % 2;
        for(int j = l; j <= r; j++){
            delta += arr[j - 1] % 2;
        }
        delta %= 2;
        if(delta == cnt){
            std::cout << "NO" << std::endl;
        }else{
            std::cout << "YES" << std::endl;
        }
    }
}
// side note, we repeatedly use "% 2" operation to avoid integer overflow
// and because it preserves properties of oddness/eveness over +, - and *
int main(){
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int tc; std::cin >> tc;
    while(tc--){
        solve();
    }
    return 0;
}

We achieve perfect results!
until test 9, where we have to process up to 200,000 inputs on one array of length 200,000

this blows up both our q and r - l term, leading to something a bit more like O(n^2), which is not ideal when we have such a large array

The prefix sum

So, we introduce the prefix sum. Instead of reading the whole array through, at any given point, we will only consider wether the sum up to that point is even or odd. This means that if we observe a change in even/oddness between l and r, we know that the sum between l and r is odd, as that is the only way even/oddness can change.

By doing this, we replace the expensive sum(arr[l], … , arr[r]) function with a simple arr[r] - arr[l].

While both of the above returns the same thing (wether the subarray sum is even or odd), arr[r] - arr[l] only takes O(1) compared to O(r - l) for the sum function. So, we save an order of magnitude of operations by simply reading in the data differently/changing the relevant data we store.

Below is my implementation of the prefix sum array, with a runtime complexity of O(n * q):

#include <iostream>
#include <cstring>

void solve() {
    int n; int q;
    std::cin >> n >> q;
    int arr[n];
    memset(arr, 0, sizeof(arr));
    for(int i = 0; i < n; i++){
        int buffer;
        std::cin >> buffer;
        if(i != 0){
            arr[i] = (buffer + arr[i-1]) %2;
        }else{
            arr[i] = buffer % 2;
        }
    }
 
    for(int i = 0; i < q; i++){
        int l, r, k;
        std::cin >> l >> r >> k;
        int delta = (r - l + 1) % 2 * (k) % 2;
        if ((l >= 2 ? arr[l-2] : 0) != arr[r - 1]){
            delta++;
        }
        if(delta % 2 == arr[n - 1]){
            std::cout << "NO" << std::endl;
        }else{
            std::cout << "YES" << std::endl;
        }
    }
}
 
int main(){
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int tc; std::cin >> tc;
    while(tc--){
        solve();
    }
    return 0;
}

The amazing thing about prefix sums is that they trade an order of magnitude of time complexity for oftentimes just a linear factor of memory. In this example, there’s actually no memory overhead whatsover! It’s important to note that prefix related functions generally work best when the following properties are satisfied in some way:

  • the basic operation is associative
  • the data is static
  • repeated computation required

As always, my contact info is listed at chenrz.com/about/ and I am always open to questions, queries and concerns.

2026-03-31