Prefix Sum
Store running totals once, and any range sum becomes two lookups and a subtraction.
Prefix Sum and Kadane: Range sum from prefix totals
Index 0 is its own total, 3.
Cost
- Best
- O(n)
- Average
- O(n)
- Worst
- O(n)
- Space
- O(n)
O(1) per query after O(n) build.
Before this
Leads to
Topics that need this one first.
Taught by the same lesson
Prefix Sum and Kadane covers these too, in the same run.