What is the prefix sum technique, and when do you reach for it?
You work out the running totals once and keep them, and then every question about a range of the array is a subtraction.
def prefix_sums(nums):
sums = [0]
for value in nums:
sums.append(sums[-1] + value)
return sums
So how does it work? The list sums holds the total of everything up to each position, so sums[3] is the total of the first three values. And the sum of the values from position a to position b is sums[b + 1] - sums[a].
So when do you reach for it? When you have many questions about ranges of the same data and the data does not change. Then you pay the cost of building the list once and every question after that is a constant amount of work.
And you reach for it in a lot of other places too. The subarray sum problem is one of them. The problem of counting how many times a prefix appears is another. And the two pointer problems often use it, because knowing the running total tells you where the other end of the answer is.
The next question in this topic asks for the shape of the structure and for when it is the wrong tool.