A prefix sum array pref[i] stores the sum of the first i elements (or of a[0..i], depending on indexing). After you build it, the sum of any contiguous slice is a subtraction.
0-based, pref[-1] treated as 0:
sum(l, r) = pref[r] - pref[l - 1]
That identity is the whole trick. Everything else is bookkeeping.
function buildPrefix(a) {
const pref = new Array(a.length);
let running = 0;
for (let i = 0; i < a.length; i++) {
running += a[i];
pref[i] = running;
}
return pref;
}
function rangeSum(pref, l, r) {
const left = l === 0 ? 0 : pref[l - 1];
return pref[r] - left;
}Kadane's algorithm (maximum subarray) is a close cousin: instead of storing every prefix, you track the best prefix ending here, and reset when it goes negative. You will implement it in the arena as Maximum Subarray.
Checks 0/2