ReviseAlgo Logo

Arrays

Prefix Sum Pattern

Master precomputed cumulative sums and difference arrays to answer range sum queries in O(1) time and solve subarray sum problems.

Last Updated: August 2, 2026 • 20 min read

1. Introduction

What is the Prefix Sum Pattern?

A Prefix Sum array precomputes the cumulative sum of elements from the start of an array up to each index.

Why is it Important?

Without precomputation, computing the sum of elements between indices L and R takes O(N) time per query. If you have Q queries, brute force takes O(Q × N) time. Prefix sum trades O(N) precomputation time and O(N) space to answer every range sum query in instant O(1) time, reducing overall query runtime to O(N + Q).

Where is it Used?

  • Financial Transaction Auditing: Calculating total account spending across any arbitrary date range instantly.
  • Image Processing (Integral Images): Computing box blur filters and GPU texture samples in real time.

    • 2. Mental Model

    Imagine a Bank Account Statement showing your running balance after every transaction.

    If you want to know how much money was deposited between Transaction #1 and Transaction #3 (inclusive):

    Sum(1 ... 3) = Balance After Tx 3 - Balance Before Tx 1 = P[4] - P[1] = 18 - 5 = 13

    You don't need to add 3 + 2 + 8 manually. You simply perform one subtraction on the running balances!

    3. Concept: Formula & Key Algorithms

    1. 1D Range Sum Query Construction & Query

    Construct a prefix array P of size N + 1, where P[0] = 0:
    P[i] = P[i - 1] + arr[i - 1]
    RangeSum(L, R) = P[R + 1] - P[L]

    2. Subarray Sum Equals K (Prefix Sum + HashMap)

    3. Difference Array for Range Updates

    4. Visuals

    Prefix Sum Construction & Lookup Diagram

    Pattern Applications

    TechniqueProblem SolvedKey Equation
    Standard Prefix SumRange Sum Queriessum(L, R) = P[R+1] - P[L]
    Prefix Sum + HashMapSubarrays with Sum = KCheck if (S_{current} - K) is in HashMap
    Difference ArrayQ Range Increment Operationsdiff[L] += val, diff[R + 1] -= val

    5. Real-World Examples

  • Range Queries in Analytics Warehouses: Pre-calculating cumulative daily metrics to report date-range sales in constant time.
  • 2D Image Box Blur (Integral Image): Computing the total pixel intensity inside any arbitrary rectangular bounding box in O(1) time.

    • 6. Interview Perspective

    How Interviewers Ask This Topic

    Look for problems involving "sum of contiguous subarray equals K", "range queries", or "product of array except self".

    Common Mistakes

    Warning: 1. Forgetting the Sentinel P[0] = 0: Creating a prefix array of size N instead of N + 1 forces clunky conditional statements when L = 0. Using size N + 1 allows P[R + 1] - P[L] to work universally!
    > 2. Forgetting Negative Numbers in Subarray Sum K: If array elements can be negative, two pointers cannot be used because sums are not monotonic! Prefix Sum + HashMap is mandatory.

    7. Summary

  • Range Sum Query: Instant O(1) query time after O(N) precomputation.
  • Sentinel Element: Always allocate size N + 1 with P[0] = 0.
  • Subarray Sum Equals K: Combine Prefix Sum with HashMap to solve in O(N) linear time even with negative numbers.
  • Difference Array: Perform range increment updates in O(1) per update, restoring the final array with a single prefix pass.

    • 8. Quiz

    Question 1: Why do we make the prefix sum array size N + 1 instead of N? Answer: To handle L = 0 gracefully without special if checks. P[0] = 0 acts as a sentinel representing the cumulative sum of 0 elements.
    Question 2: What is the formula for rangeSum(2, 5) using a 0-indexed prefix array P of size N + 1? Answer: P[6] - P[2].
    Question 3: Why can't we use Sliding Window for "Subarray Sum Equals K" if the array contains negative numbers? Answer: Sliding window requires monotonicity (expanding right increases sum; shrinking left decreases sum). Negative numbers break this assumption. Prefix Sum + HashMap works regardless of positive/negative values.
    Question 4: What is the time complexity of applying K range updates to an array of size N using a Difference Array? Answer: O(N + K). O(1) per range update × K updates = O(K), followed by a single O(N) prefix sum pass to reconstruct the array.
    Question 5: How does Prefix Sum compute "Product of Array Except Self" without using division? Answer: By computing a Prefix Product array (pref[i] = product of all elements before i) and a Suffix Product array (suff[i] = product of all elements after i), then multiplying pref[i] * suff[i].