Consider the following problem: You have a list a of numbers with N elements, as an example suppose you have 3, 4, 2, 8, -1. Someone gives you Q queries, each of the form l,r where 1<=l<=r<=N. Then, you need to output the sum of the numbers from (indexing starting at 1) from the lth index to the rth index.

We can see how to do this: loop through all the queries, create a variable x that is the sum, loop i through from l to r, and add the ith element of the list to x.

In the worst case, l=1 and r=N every single time. Then you would have to loop through N entries Q times, so the time complexity is O(NQ). This might work, but what if we say N and Q are large enough that O(NQ) fails (say 10^6)?

Motivation: We notice that we are doing the same additions many times. The queries aren't exactly independent. How can we only do the computations once? The key observation is that a[l] + ... + a[r] (if we index starting at 1) = a[1]+...+a[r] — (a[1]+...+a[l]). Now, we see what is going on: we are recomputing these values so many times!

Prefix Sums Solution: We can start by looping through all the elements and creating a list of the sum of the first x values. Then, for each query, we just need to subtract two elements in this list! So it will be O(N+Q), which is much faster than the O(NQ) we had previously.