Store cumulative totals in P, then answer any range-sum query with a single subtraction.
A simulator of prefix-sum construction and range queries
Change l and r to replay the range-sum calculation. The lower row is the prefix-sum array P.
Why does one subtraction work?
P[r+1] includes indices 0 through r, while P[l] includes 0 through l−1. Subtract the shared prefix to leave l through r. Giving P one extra entry with P[0] = 0 lets the same formula handle l = 0.
Two-dimensional prefix sums
S[i+1][j+1] = S[i][j+1] + S[i+1][j] - S[i][j] + a[i][j]
# Sum over rectangle (r1, c1) through (r2, c2)
S[r2+1][c2+1] - S[r1][c2+1] - S[r2+1][c1] + S[r1][c1]Related coding techniques
Difference arrays: to add v over [l, r], record d[l] += v and d[r+1] −= v. After all updates, prefix-sum d once. Each offline range update costs O(1).
Prefix sums + hashing: subarrays summing to K correspond to pairs with P[j] − P[i] = K. Count previously seen prefix totals in a dictionary for an O(n) solution, including inputs with negative values.