Introduction Prefix Sum Pattern

You are given an array and many queries. Each query names a range, and asks for the sum of the values inside it.

[3, 1, 4, 1, 5, 9]
sum of range 1 to 3?   1 + 4 + 1 = 6
sum of range 2 to 5?   4 + 1 + 5 + 9 = 19

Answering one query by adding the values takes O(N). A thousand queries means a thousand passes over the array. Most of them re-add the same numbers.

Do the adding once instead. Build a second array where each entry holds the total of everything up to that point.

values   3   1   4   1   5   9
prefix   3   4   8   9  14  23