Arrays &
Prefix Techniques
Precompute cumulative information to answer range queries efficiently.
What This Category Is Really About
Elements have fixed positions. Queries on [L, R] always ask about the same subsequence. This predictability enables preprocessing.
Operations compose: sums add, products multiply, XOR chains. Build cumulative results once, answer any range query without recomputation.
Range queries depend only on two boundary values. Middle elements don't matter. This locality enables O(1) queries.
"Many DSA problems start here. Once you recognize repeated questions about fixed ranges or cumulative state tracking, prefix techniques become your first instinct."
Mental Model & Invariant
Prefix thinking: compute once, query many times.
Build an auxiliary structure storing cumulative results from start to each position. Any range query becomes a simple operation on two precomputed values.
This must hold true at every index during construction.
Range Queries
Any [L, R] answered by combining two prefix values, not iterating.
Operation Constraint
Must be reversible or associative to isolate [L, R].
Complexity
O(n) preprocessing, O(1) per query.
When to Think "Array + Prefix"
wifi_tetheringStrong Signals
Multiple queries on fixed array
Sum, product, or count queries
Need faster than O(n) per query
Cumulative or running totals
lock_openConstraint Signals
Static or infrequent updates
Reversible or associative operation
Query count justifies preprocessing
Prefix Techniques You Must Master
Simple Traversal + State
Track running state as you iterate; answer queries about state at each position.
state[i] = f(state[i-1], arr[i])
Prefix Sum
Answer range sum queries in O(1) after O(n) preprocessing.
prefix[i] = arr[0] + ... + arr[i]
Prefix Sum + HashMap
Find subarrays with specific cumulative properties without nested loops.
If prefix[j] - prefix[i] = target, then sum(i+1, j) = target.
Prefix / Suffix Products
Compute products or results that depend on elements before and after a position.
prefix[i] = prod(0, i); suffix[i] = prod(i, n-1)
Difference Array
Apply multiple range updates efficiently (diff[L]+=v, diff[R+1]-=v), then prefix sum recoveries.
diff[i] = arr[i] - arr[i-1]
Cumulative Frequency
Track how many elements satisfy a condition up to each position.
freq[i] = count(arr[0..i] meets cond)
How to Learn These Techniques
Understand Brute Force
Write how you'd answer a query by iterating the range. Identify what computation repeats.
Identify What Accumulates
Determine which operation can be precomputed. Verify it's reversible or associative.
State the Invariant
Write exactly what each prefix position stores. This must be true at every step.
Verify on a Small Example
Trace your formula on paper with explicit indices before coding.
State complexity trade-offs
O(n) preprocessing vs O(1) query. Trading O(n) space for speed.
Canonical Problem List
folder_openFoundation
Range Sum Query
Direct application of prefix sum; establishes the core pattern.
Subarray Sum Equals K
Combines prefix sum with hash map; teaches state lookup.
Running Sum of 1D Array
Simple traversal with state; builds intuition for accumulation.
Find Pivot Index
Uses prefix and suffix sums to find a balance point.
folder_openIntermediate
Product of Array Except Self
Classic prefix and suffix products problem; avoids division.
Range Sum Query 2D
Extends prefix sum to 2D matrices; teaches generalization.
Contiguous Array
Transforms problem into prefix sum with hash map lookup.
Range Addition
Introduces difference arrays for efficient range updates.
folder_openAdvanced
Maximum Sum Rectangle
2D prefix sum combined with Kadane's algorithm.
Count Subarrays with Sum in Range
Prefix sum with binary search or a two-pointer approach.
Bounded Max Subarrays
Combines prefix logic with constraint tracking.
Trapping Rain Water
Prefix and suffix maxima; applies to 1D geometry.
Common Mistakes
Off-by-one errors in range queries
Confusion about inclusive vs. exclusive bounds; prefix array indexing mismatch.
Trace your formula on paper with explicit indices before coding.
Prefix on non-reversible operations
Query formula fails; cannot isolate range [L, R] from full prefix results.
Verify operation is reversible (subtraction) or associative before applying prefix.
Forgetting to handle the L=0 case
Query with L=0 accesses prefix[-1], causing index out of bounds.
Add a dummy prefix[0] = 0 or handle L=0 as a special case explicitly.
Rebuilding prefix array on every update
Each update takes O(n); total time becomes O(n × updates).
Use difference array for batch updates or Segment Trees for frequent updates.
Interview Guidance
What they test
- ✎Preprocessing trade-offs: space vs speed
- ✎Thinking in invariants before coding
- ✎Verifying edge cases analytically
Clarity Signals
Explaining a prefix approach demonstrates thinking in invariants, not just code. Articulate what each position stores and why the formula works to signal disciplined thinking.
Verbal Template
"Double down on constraints. Mention brute force is O(n) per query."
"Clearly state: 'My invariant is prefix[i] = cumulative op.'"
"Trace a 3-element example out loud with indices."
"Confirm complexity is O(N) prep and O(1) query."
When You've Mastered It
Pattern recognition is immediate
Invariant is written before code
Edge cases (L=0) verified by hand
Operation reversibility verified
Choosing right technique (diff array vs tree)
Reasoning from first principles
What This Unlocks Next
Sliding Window
Extends prefix thinking to dynamic windows that expand and contract.
Binary Search
Answers 'where is the boundary?' while prefix answers 'what's the state?'
Segment Trees
Generalizes prefix sum to O(log N) updates for dynamic arrays.
Two Pointers
Uses movement instead of prep to avoid redundant iteration.
"The pattern is always the same: identify what accumulates, store it, answer efficiently."