Sum Any Range with Subtraction
Answer range[l..r] in constant time.
The Real Payoff
Building the prefix array was the setup. Now comes the magic: answering any range sum with a single subtraction. ⚡
The Core Idea
A range sum is just one big total minus a smaller one. Subtracting two prefix values cancels everything outside your range cleanly.
All lessons in this course
- Build a Prefix Sum Array
- Sum Any Range with Subtraction
- Count Subarrays with a Target Sum
- Difference Arrays for Range Updates