What is a Prefix Sum?
A prefix sum (also called cumulative sum) is a simple but powerful concept: at each position in an array, we store the sum of all elements up to that position. Think of it like keeping a running total as you move through the array. Letās see a simple example:
Hereās how we build a prefix sum array:
Why are Prefix Sums Useful?
The real power of prefix sums comes when we need to calculate the sum of any range in the array. Letās say we want the sum of elements from index i to j. Without prefix sums, weād need to loop through all elements in that range. With prefix sums, we can do it in O(1) time using this formula: Sum(i to j) = prefix[j] - prefix[i-1] (if i > 0) or prefix[j] (if i = 0) Hereās a practical example: