1 · Model, solve and test · 25 MIN

Answer range totals with prefix sums

Answer range totals with prefix sums

Repeated range queries can reuse a single cumulative summary. Prefix position i stores the sum of values strictly before i, with prefix[0] equal to zero. A half-open query [start,end) is prefix[end] minus prefix[start]. Building the summary costs one scan, then each query takes constant time. The contract uses valid indices and safe integer totals; validation belongs at an external input boundary.

Make the cumulative array one item longer than the input.

Read the example

function solve(input){const prefix=[0];for(const value of input.values)prefix.push(prefix.at(-1)+value);return input.queries.map(([start,end])=>prefix[end]-prefix[start])}
console.log(JSON.stringify(solve({"values":[2,3,-1,4],"queries":[[0,4],[1,3],[2,2]]})));

[8,2,0]

Your challenge

Input is {values:number[],queries:[start,end][]}. Return the sum for each half-open range [start,end), including empty ranges, without mutating input.

Solution cost: O(n + q) preprocessing and q queries. time · O(n + q) prefix summary and results. space

Common trap

Inclusive and half-open endpoints use different formulas; never mix their contracts.