AI engineering glossary · Data structures algorithms
What is prefix sum?
Prefix sum (also called cumulative sum): An array in which each entry holds the total of all items up to that position, computed once in O(n). The sum of any range is then found in O(1) as a difference of two prefix values.
Prefix sum: an example
For [3, 1, 4, 2] the prefix sums are [3, 4, 8, 10]. The sum of positions 2 to 3 is 10 - 4 = 6.
Related terms
More Data structures algorithms terms
- Prim's algorithm
- Priority queue
- Queue
- Quickselect
- Quicksort
- Radix sort
- Randomized algorithm
- Recurrence relation
Where you learn it
Prefix sum is part of the AI Engineering Program, which teaches it with notes, a hands-on lab and an exam. The first lesson is free.