Revenue between any two days
The dashboard asks "revenue from day 30 to day 90?" thousands of times. Store a prefix sum — pre[i] is the total of the first i days — and every range total is just pre[to + 1] - pre[from].
Prefix sums and counting subarrays
const revenue = [120, 80, 200, 50, 300, 90];
const pre = [0];
for (const r of revenue) pre.push(pre[pre.length - 1] + r);
console.log(pre);
const rangeSum = (from, to) => pre[to + 1] - pre[from];
console.log(rangeSum(1, 3), rangeSum(0, 5));
// How many contiguous stretches add up to exactly k? Count earlier prefixes equal to (current - k).
function countSubarrays(nums, k) {
const seen = new Map([[0, 1]]);
let sum = 0, count = 0;
for (const n of nums) {
sum += n;
count += seen.get(sum - k) ?? 0;
seen.set(sum, (seen.get(sum) ?? 0) + 1);
}
return count;
}
console.log(countSubarrays([1, 2, 3, -2, 2], 3));The 2-D version (summed-area tables) answers rectangle sums in images and heatmaps the same way.