Prefix Sums and Difference Arrays

Store the work before the query

Define prefix[i] as the sum of the first i values, with prefix[0] = 0. Then the inclusive range from left through right is:

prefix[right + 1] − prefix[left]

The extra leading zero removes special handling when left is 0. Building the array costs O(n); every range query then costs O(1).

More than sums

The same shape supports prefix XOR, counts of a character, and cumulative frequencies. Two-dimensional prefix sums answer rectangle totals using inclusion–exclusion: add the large prefix, subtract the two outside strips, then add back the overlap removed twice.

Not every operation has an inverse. Minimum and maximum cannot generally be removed by subtracting prefixes; use a sparse table or segment tree instead.

Range updates with differences

A difference array reverses the idea. To add x to every index in [left,right], add x at left and subtract x at right+1 when it exists. One final prefix scan materialises every update. This changes q range updates from O(nq) to O(n + q).

Range sum example

a=[2,4,1,3]; p=[0]
for x in a: p.append(p[-1]+x)
print(p[4]-p[1])

8

When updates and queries mix

Static prefixes become stale after an update. Use a Fenwick tree for prefix-combinable point updates, a segment tree for general interval summaries, or offline sorting when query order does not matter.

Practice Range Sum Queries, then continue to Dynamic Range Sums with a Fenwick Tree.