Prefix sums

A prefix array stores cumulative boundaries

A prefix-sum array converts repeated range-sum questions into differences between cumulative totals. The extra initial zero represents the boundary before the first value. Half-open ranges then use one consistent rule: the sum from index left inclusive to right exclusive is prefix[right] minus prefix[left]. The original sample does not define a reusable range-checking API, so callers extending it must still validate boundaries. The stored cumulative totals describe the input at construction time rather than automatically following later array edits.

Build every boundary before subtracting

For values two, four, six, and eight, the prefix array becomes zero, two, six, twelve, twenty. The first print subtracts prefix[1] from prefix[3], giving twelve minus two equals ten. That range contains original indices one and two, whose values are four and six. The second print subtracts zero from twenty and reports the full-array total. The expected output is therefore 10 and 20. Writing the entire prefix array first makes both the arithmetic and the index convention independently inspectable.

prefix[3] - prefix[1]

Subtract the part before the desired range

Prefix[right] includes all source values before right. Prefix[left] includes exactly the earlier values that should be excluded. Their difference retains only the desired half-open range, so each valid query uses a constant number of array accesses and arithmetic operations after preprocessing. The loop establishes prefix[i + 1] as the cumulative sum through source index i. Using long storage gives a wider accumulator than the int input elements, and choosing another input type would require reviewing the corresponding numeric bounds.

Inclusive endpoint language causes off-by-one errors

A request for indices one through three inclusive is not the range [1,3); it needs right equal to four under this convention. Mixing those descriptions can produce a plausible but incomplete total. The extra zero slot avoids special subtraction code for a range starting at zero, but it does not validate reversed or out-of-bounds arguments. Keep the mathematical range notation, user-facing index language, and actual array bounds aligned instead of fixing individual failures with unexplained plus-one adjustments.

Practice: cover empty and single-element queries

Using the unchanged prefix array, calculate the first element, last element, whole array, and an empty range whose two boundaries are equal. Predict two, eight, twenty, and zero. Then write a small RangeSum helper requiring zero less than or equal to left, left less than or equal to right, and right no greater than the input length. Test one reversed range and one out-of-bounds range to ensure they are rejected rather than interpreted as valid negative or accidental totals.

• Write every requested range in [left,right) notation before converting it to prefix indices.
• An empty range is a valid zero sum when the stated API permits equal boundaries.

Practice: expose the preprocessing lifetime

For an independent change, build prefix first and then change the original second value from four to forty. The old range query still reports ten because its stored boundaries were not rebuilt. Construct a new prefix array and verify that the same [1,3) query now reports forty-six, while the full total becomes fifty-six. This experiment distinguishes an immutable historical calculation from a live data structure. A system requiring efficient updates needs a different design, not an assumption that an ordinary array remembers where its numbers came from.

• Decide who owns rebuilding cumulative state after permitted source edits.
• Compare preprocessing plus query costs with a direct sum when the application asks only one small question.

Specify both the index convention and the data version

Prefix sums are useful when many range queries share one stable input version. Preprocessing and storage are linear in input length, while each valid query is constant work. Those benefits depend on the half-open boundary contract and the lifetime of the prepared array. The sample’s local managed arithmetic is supported in the browser runtime and its totals can be checked by hand. When adapting it, retain explicit range validation, numeric-type reasoning, and source-update policy so a fast answer remains an answer about the intended interval and data version.

• Baseline prefix values are zero, two, six, twelve, twenty.
• The displayed ten is four plus six, and the displayed twenty is the full sum.
• A prefix array is prepared state; source mutation does not automatically recompute it.