Algorithms and Data Structures · Junior · Question 67 of 75
What is a prefix sum array?
- 1An array of the first characters of each string
- ✓Correct answer: Element
iholds the sum of the firstioriginal elements - 3The original array, sorted in ascending order once
Explanation
After one O(n) pass, the sum of any range [l, r) is prefix[r] - prefix[l] in O(1). It's the go-to trick when the same array is queried for many range sums.