Dynamic Programming21 sections · 916 units
Open in Course

Static Range Sum Queries - The Formula

Prefix[r] - prefix[l-1]

Let prefix[0] = 0 for convenience. Then prefix[i] = prefix[i-1] + arr[i] for i from 11 to nn. Query [a,b]: answer = prefix[b] - prefix[a-1]. The off-by-one is easy to get wrong.

Double-check with a small example. Example: arr = [1,3,4,8], prefix = [0,1,4,8,16]. Sum of [2,4] = prefix[4] - prefix[1] = 16 - 1 = 15 = 3+4+8. ✓ This formula works because prefix sums telescope: adding and subtracting adjacent terms cancels out.