Range Sum Query
The sum of a range is the total up to its end minus the total before its start.
Prefix Sum and Kadane: Range sum from prefix totals
Sum of 2 to 5 is prefix[5] minus prefix[1]: everything up to 5, less everything before 2.
Cost
- Best
- O(1)
- Average
- O(1)
- Worst
- O(1)
- Space
- O(n)
After O(n) preprocessing.
Before this
Related
Taught by the same lesson
Prefix Sum and Kadane covers these too, in the same run.