Prefix Sum

Precompute cumulative aggregates so range answers can be derived in constant time.

Precompute cumulative aggregates so range answers can be derived in constant time.

The prefix array always holds the cumulative aggregate up to each index while the input remains unchanged.

Any sub-array aggregate equals the prefix value at the right boundary minus the prefix value just before the left boundary.

The O(n) precomputation is amortized over O(1) per query.