Prefix Sums & Difference Arrays for Constant-Time Range Queries

When dealing with frequent range sum queries or bulk range updates on an array, naive solutions require $O(n)$ per query, resulting in an unscalable $O(n \times q)$ for $q$ queries. Prefix Sum Arrays solve range sum queries in $O(1)$ constant time, while Difference Arrays apply range updates across intervals in $O(1)$ constant time.

1. Real-World Analogy: The Odometer & Ledger

Imagine tracking your car's fuel expenses:

• Instead of writing down how much you spent on every 5 km interval and adding them up every time someone asks your expenses between day 10 and day 20, you record your running cumulative total at the end of every day.
• To find spending between Day $L$ and Day $R$, you simply compute:

$$\text{Total}(L \to R) = \text{Odometer}(R) - \text{Odometer}(L - 1)$$ A single subtraction gives you the exact total instantly!

2. Prefix Sum Array Construction & Formula

Given an array arr: $$\text{prefix}[0] = \text{arr}[0]$$ $$\text{prefix}[i] = \text{prefix}[i - 1] + \text{arr}[i]$$

Range Sum Query Formula (Inclusive indices $L$ to $R$):

$$\text{Sum}(L, R) = \begin{cases} \text{prefix}[R] & \text{if } L = 0 \\ \text{prefix}[R] - \text{prefix}[L - 1] & \text{if } L > 0 \end{cases}$$

3. Difference Arrays: $O(1)$ Range Updates

Suppose you need to add $+V$ to all elements in range $[L, R]$ for 100,000 queries:

• Naive loop: $O(R - L) \approx O(n)$ per update.
• Difference Array Technique:

1. 1
   $\text{diff}[L] \mathrel{+}= V$ (marks the start of the increment)
2. 2
   $\text{diff}[R + 1] \mathrel{-}= V$ (cancels out the increment after the boundary!)
3. 3
   After all $q$ queries, compute the prefix sum of the difference array in a single $O(n)$ pass!

4. Multi-Language Implementations: Prefix Sum Class

Python 3:

Modern JavaScript / TypeScript:

5. Trace Table: Range Updates via Difference Array

Initial Array of size 5: [0, 0, 0, 0, 0]

• Query 1: Add $+10$ to range $[1, 3]$
• Query 2: Add $+5$ to range $[2, 4]$

Resulting array [0, 10, 15, 15, 5] generated with zero looping per query!