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.
Articles by others on the same topic
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\).