A **prefix sum** is a concept used in computer science and mathematics, particularly in the context of array manipulation and analysis. The prefix sum of an array is a new array where each element at index \(i\) represents the sum of the elements in the original array from the start up to index \(i\).
Articles by others on the same topic
The prefix sums can all be computed by the recurrence in linear time. Any contiguous sum is then , so it takes constant time after preprocessing.