Precompute running totals once; answer any range sum in O(1).
Range sum
—
sum […]
Legend
prefix[r]
prefix[l−1]
AI Tutor Workspace
—
In a nutshell
A prefix-sum array stores, at each position, the running total of everything up to that point. Build it once in a single pass. After that, the sum of any stretch is just the total at its right end minus the total just before its left end — one subtraction, no matter how long the stretch. It trades a little upfront work for instant answers to many range-sum questions.
Ready
Press play to begin the cinematic walkthrough.
Precompute running totals once; then any range sum is just prefix[r] − prefix[l−1] — O(1) per query instead of O(n).