Running Sum of 1d Array

What it tests

The base building block: cumulative sums.

Approach & answer

Carry a running total, writing it at each index. This precomputation is what makes any range-sum query O(1) later: sum(i..j) becomes prefix[j] − prefix[i−1]. Doing it in place mutates the input to O(1) extra space; keep a separate output array if the caller still needs the originals. Trivial on its own, but it's the foundation the harder prefix-sum problems build on — the difference of two cumulative sums is the whole trick.

Use this technique when

Foundation for range queries and 'sum so far' problems.

Complexity

Time O(n) · Space O(1) (in place)

References

• LeetCode 1480 · Running Sum of 1d Array