Prefix Sums

The Idea

Precompute running totals so that prefix[i] holds the sum of everything before index i. Any range sum then becomes a single subtraction. You build in O(n) and answer each query in O(1).

Real-World Example

A bank statement shows a running balance after every transaction. To see what you spent in March, you subtract the balance on March 1 from the balance on April 1 instead of re-adding every purchase.

The Code

def build_prefix(nums):
    prefix = [0]
    for x in nums:
        prefix.append(prefix[-1] + x)   # running total
    return prefix

def range_sum(prefix, i, j):
    # sum of nums[i..j] inclusive, in O(1)
    return prefix[j + 1] - prefix[i]

p = build_prefix([3, 1, 4, 1, 5])   # [0, 3, 4, 8, 9, 14]
print(range_sum(p, 1, 3))           # 1 + 4 + 1 = 6

nums   = [2, 4, 6]
prefix = [0, 2, 6, 12]
# sum of nums[1..2] should be 10
total = prefix[3] - prefix[___]