Prefix Sum

A precomputation strategy, where you preprocess and store the sum upto each element before hand, so that, when required in the actual computation, these sums can be quickly queried.

For example:

• Array: [1,2,3,4,5,6,7]
• Prefix Sum Array: [1,3,6,10,15,21,28]