Intermediate · Module 8 · Lesson 3
Difference arrays
Apply many range updates efficiently.
15–25 min readLesson 44 of 123
Lesson 44 of 123
1d streakTheory lesson · Step-by-step
Understand Difference arrays
Apply many range updates efficiently.
Worked approach
Trace the reasoning step by step
- 1For update [left,right] by delta, add delta at left.
- 2Subtract delta at right + 1 when it exists.
- 3After all updates, take a prefix sum.
- 4The reconstructed values contain every range contribution.
Concrete example
Add 3 to indexes 1…3 of a zero array length 5.
- 1diff[1] += 3.
- 2diff[4] -= 3.
- 3Prefix-sum the difference array.
The final values are [0,3,3,3,0].
What must remain true (Loop Invariant)
The difference array stores where each range contribution starts and stops.
Cost Model
Complexity & Trade-offs
OperationTimeSpaceWhy
Range update / materialize
O(1) / O(n)
O(n)
Useful when updates are batched before reads.When to use it
- Range queries, range updates, directional products, and best contiguous scores.
- Replacing repeated range scans with cumulative state.
- Combining left and right summaries.
Common mistakes
- Mixing inclusive and exclusive prefix conventions.
- Using zero as Kadane’s base when a non-empty all-negative answer is required.
- Subtracting the wrong boundary or forgetting a neutral prefix.
Practice prompts
- Reproduce the worked Difference arrays example without looking at the trace.
- Change one input condition and explain whether the Difference arrays invariant still holds.
- Implement the approach, derive its cost, and compare it with a straightforward baseline.
Mastery check
Can you derive it instead of memorizing it?
State the invariant before looking at code.
Explain why every transition is safe.
Construct a worst-case input.
Name one alternative and its trade-off.