Prefix sums

O(n) build / O(1) query

Precompute a running total once, `prefix[i]` = sum of the first i elements, so the sum of any range `[l, r]` becomes a single subtraction instead of a rescan.

Signals

many sum-over-a-range queriesanswer several range-sum questions on the same arraysum from index l to rrunning total or cumulative sum

Template

function buildPrefix(arr) {
    const prefix = new Array(arr.length + 1).fill(0);
    for (let i = 0; i < arr.length; i++) {
        prefix[i + 1] = prefix[i] + arr[i];
    }
    return prefix;
}
function rangeSum(prefix, l, r) {
    return prefix[r + 1] - prefix[l]; // sum of arr[l..r]
}

Looks similar, isn't

Variable sliding window: A window makes one forward pass to find the single best contiguous span. Prefix sums precompute once so you can answer many arbitrary, unrelated ranges afterward, not just one best span.
Difference array: Prefix sums answer many range READS on a fixed array. A difference array is for the opposite direction: many range UPDATES applied first, with one final read at the end.

n up to 1e5..1e6 with many queries -> O(n) to build the prefix array once, then O(1) per range-sum query instead of O(n) per query.

Learn this pattern