Algorithms / Prefix Sums

Least You Need to Know: Prefix Sums, Range Aggregates, and Subtracting History

Prefix sums precompute cumulative totals so a range sum becomes **one subtraction of two histories**. This is one of the highest-leverage preprocessing tricks in algorithmic problem solving.

جو کم از کم جاننا ضروری ہے

A prefix sum stores the aggregate of the first part of an array.
Range sum on `[l, r]` becomes `prefix[r] - prefix[l-1]` with 1-based indexing.
Building prefixes costs linear time and space.
Prefix ideas extend beyond sums to counts and other additive quantities.
Prefix preprocessing is best for many queries on mostly static data.

اہم علامتیں

pref[i] sum of elements up to index i

range(l, r) aggregate over a contiguous interval

pref[r] - pref[l-1] range-sum query by subtraction

مختصر حل شدہ مثال

For array `[2, 5, 1, 4]`, the prefix sums are `[2, 7, 8, 12]`.
The range sum from index `2` to `4` is `12 - 2 = 10`.
Instead of re-adding the interval each time, reuse the cumulative totals.
That is the main speedup provided by prefix sums.

عام غلطیاں

Off-by-one mistakes are common around whether `pref[0]` is defined as zero.
Prefix sums help most when the array is static or updates are rare.
The trick requires an additive-like combine operation for simple subtraction.

اس قسم کے سوال کو کیسے پہچانیں

There are many interval-sum or interval-count queries on a static array.
The problem asks for cumulative totals from the beginning up to each position.
A direct re-scan of every query would be too slow.