DSA & Algorithms
Part 4 of 21 · DSA Interview PatternsPrefix Sums & Difference Arrays — Range Queries in O(1)
Prefix sums and difference arrays for range sums and range updates.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
You will ask for many ranges, or apply many range updates
Prefer
Pay O(n) once, then O(1) per range
A prefix stores the sum to the left of each index. A difference array stores range edits and becomes the array after one scan.
- Inclusive ranges need the extra leading zero.
- Subarray sum K is a hash of prefixes, not a window, when negatives exist.
- Range updates stay O(1) until you materialize the result.
Alternative
Loop the range every time
Fine for one query. Painful for Q queries or Q updates.
- Off-by-one on inclusive ends.
- A difference array with no final prefix pass.
- A sliding window on a sum that may be negative.
Build, then query
Prefix for reads. Difference array for stacked range writes.
- 1
Build the prefix
P[0] = 0 and P[i+1] = P[i] + nums[i]. - 2
Subtract the left edge
Sum from i through j is P[j+1] - P[i]. - 3
Or edit a difference array
Add at L, subtract at R+1, then prefix once.
Overview
Prefix sums and difference arrays for range sums and range updates.
Below is the full pattern: when to reach for it, a top-down picture, runnable Python and TypeScript templates, complexity, traps, LeetCode drills, and Q&A.
When to use / recognition cues
Use when you need many range sum queries, or range updates then a final point query pass.
Recognition cues
- subarray sum equals K
- range sum immutable
- add val on [L,R] many times then read array
- 2D matrix region sums
Mental model
Flow
- 1
1. Build prefix P
- next2. Query range i..j
- 2
2. Query range i..j
- next3. P at j+1 minus P at i
- 3
3. P at j+1 minus P at i
- next4. Or start a diff array
- 4
4. Or start a diff array
- next5. Add at L, subtract at R+1
- 5
5. Add at L, subtract at R+1
- next6. Prefix of diff is the array
- 6
6. Prefix of diff is the array
Lesson map
Prefix Sums & Difference Arrays — Range Queries in O(1)
Prefix sums and difference arrays for range sums and range updates.
Architecture. 1. Build prefix P Ready. 2. Query range i..j Ready. 3. P at j+1 minus P at i Ready. 4. Or start a diff array Ready. 5. Add at L, subtract at R+1 Ready. 6. Prefix of diff is the array Ready
Select a node to see why it exists, or an edge to see the protocol, direction, effect, and consequence.
Mermaid export
flowchart TB A["1. Build prefix P Ready"] B["2. Query range i..j Ready"] C["3. P at j+1 minus P at i Ready"] D["4. Or start a diff array Ready"] E["5. Add at L, subtract at R+1 Ready"] F["6. Prefix of diff is the array Ready"] A -->|continues| B B -->|continues| C C -->|continues| D D -->|continues| E E -->|continues| F
Read the chart from top to bottom. Two-way decisions keep the card narrow on a phone.
Core template (Python)
Press Run. Snippets must be self-contained — no network, files, or native modules.
Core template (TypeScript)
Press Run. Snippets must be self-contained — no network, files, or native modules.
Complexity analysis
- Build prefix O(n); each range sum O(1).
- Difference: O(1) per update, O(n) finalize.
- Subarray sum equals K with hashmap: O(n) time/space.
Common pitfalls & interview traps
LeetCode drill (real problems)
- Range Sum Query - Immutable
- Subarray Sum Equals K
- Product of Array Except Self
- Corporate Flight Bookings
- Range Sum Query 2D - Immutable
- Contiguous Array
Go deeper
- Back to the pattern map.
- NeetCode roadmap
- CP-Algorithms
Interview Q&A
Prefix vs fenwick/segment?
Answer
Prefix for static arrays; fenwick/seg for point updates plus range queries.
Subarray sum = K approach?
Answer
Hash count of prefix values seeded with {0: 1}; at each prefix s add count[s - K] first, then increment count[s].
Difference array use case?
Answer
Many range increments, few reads of the final array.
2D formula?
Answer
P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1].
Why +1 length prefix?
Answer
Clean empty-prefix zero; avoids special-casing i=0.
Negatives OK?
Answer
Yes for prefix; sliding-window sum shrink may fail with negatives.