Sign in to watch this lesson
Algorithms - Arrays · 4:17
Prefix Sums
Running totals drawn as a staircase: with P[0] = 0 and P[i] = P[i-1] + a[i-1], the sum of any half-open range [l, r) is the difference of two heights, P[r] - P[l], in constant time after one linear pass. We race 100,000 range queries on a Mac (a naive loop doing 3.3 billion additions versus prefix sums), answer queries given as timestamps with lower_bound and upper_bound, extend the idea to XOR and counts, see why minimum breaks it, and catch the int overflow that a prefix array invites.
You will learn
- Build a prefix sum array with the sentinel P[0] = 0 and answer half-open range sums as P[r] - P[l]
- Convert value-based queries (timestamps) into index ranges with lower_bound and upper_bound
- Recognise which operations prefix sums support (sum, XOR, counts) and why min/max need other structures
- Avoid overflow and off-by-one errors by using long long prefix arrays and a consistent half-open convention