Prefix Sum Basics

Introduction

Prefix Sum is a fundamental technique for efficiently calculating the sum of elements within various subarrays (ranges) of an array. It involves precomputing cumulative sums, allowing subsequent range sum queries to be answered in constant time. This pattern is crucial for optimizing solutions to many array-based problems.

Quick Overview

Precomputing cumulative sums to answer range sum queries in O(1) time after an O(N) setup.

Motivation

When dealing with an array, calculating the sum of elements within a specific range [i, j] naively requires iterating from i to j, taking O(j-i+1) time. If multiple such range sum queries are performed, the total time complexity quickly becomes O(Q*N) for Q queries on an array of size N. This inefficiency makes brute-force approaches impractical for large datasets or stringent time limits, necessitating a more optimized solution.

Real Life Analogy

Imagine you have a daily sales report for a month, showing sales figures for each day. If your manager frequently asks for the total sales between day 5 and day 10, or day 12 and day 20, you wouldn't want to add up each day's sales every single time. Instead, you'd create a running total: a 'cumulative sales' report. This report lists the total sales from day 1 up to each specific day. To find sales between day 5 and day 10, you simply take the cumulative sales up to day 10 and subtract the cumulative sales up to day 4. This is much faster than summing individual days.

Core Idea

The core idea of Prefix Sum is to create an auxiliary array, P, where P[i] stores the sum of the first i elements of the original array A. That is, P[i] = A[0] + A[1] + ... + A[i-1]. With this precomputed array, the sum of any subarray A[left...right] (inclusive) can be calculated in O(1) time as P[right + 1] - P[left]. A common convention is to set P[0] = 0 to simplify calculations for ranges starting at index 0.

Key Insight

The 'aha!' moment is realizing that any subarray sum sum(A[left...right]) can be expressed as a difference of two precomputed prefix sums: PrefixSum[right+1] - PrefixSum[left]. This transforms an O(N) query into an O(1) lookup after an initial O(N) precomputation.

Prerequisites

• Basic array manipulation and indexing (0-indexed vs 1-indexed).
• Understanding of loops and iteration.
• Familiarity with time and space complexity analysis (Big O notation).

Visualization

Original Array A:         [ 1,  2,  3,  4,  5 ] (N=5)
Indices:                 0   1   2   3   4

Prefix Sum Array P (size N+1):
P[0] = 0
P[1] = A[0] = 1
P[2] = A[0]+A[1] = 1+2 = 3
P[3] = A[0]+A[1]+A[2] = 1+2+3 = 6
P[4] = A[0]+A[1]+A[2]+A[3] = 1+2+3+4 = 10
P[5] = A[0]+A[1]+A[2]+A[3]+A[4] = 1+2+3+4+5 = 15

P:                       [ 0,  1,  3,  6, 10, 15 ]
Indices:                 0   1   2   3   4   5

To find sum(A[1...3]):  A[1] + A[2] + A[3] = 2 + 3 + 4 = 9
Using P:                 P[3+1] - P[1] = P[4] - P[1] = 10 - 1 = 9

Dry Run

Let's trace the creation and use of a prefix sum array for A = [5, 1, 8, 2].

1. Initialization: Create a prefixSum array of size N+1 (where N is the length of A, which is 4). Initialize prefixSum[0] to 0. prefixSum = [0, _, _, _, _]

2. Building the Prefix Sum Array:

• i = 0: prefixSum[1] = prefixSum[0] + A[0] = 0 + 5 = 5 prefixSum = [0, 5, _, _, _]
• i = 1: prefixSum[2] = prefixSum[1] + A[1] = 5 + 1 = 6 prefixSum = [0, 5, 6, _, _]
• i = 2: prefixSum[3] = prefixSum[2] + A[2] = 6 + 8 = 14 prefixSum = [0, 5, 6, 14, _]
• i = 3: prefixSum[4] = prefixSum[3] + A[3] = 14 + 2 = 16 prefixSum = [0, 5, 6, 14, 16]

3. Querying a Range Sum (e.g., sum of A[1...3] inclusive):

• We want A[1] + A[2] + A[3] = 1 + 8 + 2 = 11.
• Using prefix sums: sum(A[left...right]) = prefixSum[right + 1] - prefixSum[left]
• Here, left = 1, right = 3.
• prefixSum[3 + 1] - prefixSum[1] = prefixSum[4] - prefixSum[1]
• 16 - 5 = 11. The result matches the direct sum, demonstrating the efficiency.

Algorithm

• Initialize a prefixSum array of size N + 1, where N is the length of the original array A.
• Set prefixSum[0] = 0.
• Iterate from i = 0 to N - 1 (inclusive) for the original array A.
• For each i, calculate prefixSum[i + 1] = prefixSum[i] + A[i].
• To query the sum of A[left...right] (inclusive, 0-indexed): return prefixSum[right + 1] - prefixSum[left].

Pseudocode

function buildPrefixSumArray(arr):
  n = length(arr)
  prefixSum = array of size n + 1
  prefixSum[0] = 0  // Initialize with 0 to handle sums starting from index 0
  for i from 0 to n-1:
    prefixSum[i+1] = prefixSum[i] + arr[i]
  return prefixSum

function queryRangeSum(prefixSum, left, right):
  // 'left' and 'right' are 0-indexed bounds for the original array
  // sum(arr[left...right]) = (arr[0] + ... + arr[right]) - (arr[0] + ... + arr[left-1])
  // This maps to prefixSum[right+1] - prefixSum[left]
  
  // Ensure valid indices, though usually handled by problem constraints
  if left < 0 or right >= length(prefixSum) - 1 or left > right:
    return ERROR_OR_HANDLE_INVALID_RANGE
    
  return prefixSum[right + 1] - prefixSum[left]

Time Complexity

O(N) for construction, O(1) for each query - Building the prefix sum array requires a single pass through the input array, taking O(N) time. Once constructed, any range sum query involves two array lookups and one subtraction, which are constant time operations, O(1).

Space Complexity

O(N) - An additional array of size N+1 is created to store the prefix sums, where N is the size of the original array. This auxiliary space is directly proportional to the input size.

Advantages

• Efficient Querying: Provides O(1) time complexity for each range sum query after initial setup.
• Simplicity: The core logic is straightforward to understand and implement.
• Versatility: Forms the basis for more advanced techniques (e.g., 2D prefix sums, difference arrays, hash map optimizations for specific sum problems).

Limitations

• Requires Additional Space: The O(N) space complexity might be a concern for extremely large arrays if memory is strictly limited.
• Static Array: If the original array is frequently updated (elements change), the prefix sum array needs to be recomputed or dynamically maintained, which can negate the O(1) query advantage. For dynamic updates, Fenwick Trees (BITs) or Segment Trees are more appropriate.
• Limited to Associative Operations: Primarily works for operations like sum, product, XOR, where op(a, b, c) = op(op(a, b), c). Does not directly apply to non-associative operations like median or mode.

Common Mistakes

• Off-by-one errors: Incorrectly using prefixSum[i] instead of prefixSum[i+1] or prefixSum[left-1] instead of prefixSum[left], especially when handling 0-indexed vs 1-indexed original arrays.
• Not initializing prefixSum[0] = 0: This leads to incorrect sums for ranges starting at index 0.
• Incorrectly handling left = 0: If prefixSum[left-1] is used without the prefixSum[0]=0 convention, an out-of-bounds error or incorrect sum will occur.
• Forgetting about integer overflow: When summing a large number of elements or elements with large values, the sum can exceed the maximum value for standard integer types (e.g., int in C++/Java), requiring long long or long.

Edge Cases

• Empty array: The prefix sum array will just be [0] (or null/empty depending on implementation).
• Single-element array: A = [val]. prefixSum = [0, val]. Query A[0...0] would be prefixSum[1] - prefixSum[0] = val - 0 = val.
• Query range left == right: sum(A[i...i]) should yield A[i]. Using formula: prefixSum[i+1] - prefixSum[i] = A[i], which is correct.
• Query range starts at index 0: sum(A[0...right]) = prefixSum[right+1] - prefixSum[0] = prefixSum[right+1].
• Query range spans the entire array: sum(A[0...N-1]) = prefixSum[N] - prefixSum[0] = prefixSum[N].

Recognition Tricks

• Problems asking for the sum of elements in subarrays or ranges.
• Problems involving multiple queries for subarray sums.
• Finding a subarray with a specific sum or property related to its sum (often combined with a hash map).
• Questions where a fixed-size window (sliding window) needs its sum updated efficiently.
• When a property for a segment [i, j] can be derived from the property of [0, j] and [0, i-1] (e.g., P(i, j) = P(0, j) - P(0, i-1)).

When To Use

• When you need to perform many range sum queries on an array that does not change frequently.
• As a precursor to more complex array problems involving subarray sums or properties related to cumulative values (e.g., finding the longest subarray with sum K).
• In 2D scenarios, for calculating sums within submatrices (2D Prefix Sums).
• When constant-time range queries are critical for overall solution efficiency.

Interview Perspective

Prefix Sum is a foundational pattern frequently tested in interviews to assess a candidate's understanding of basic optimization techniques. Interviewers look for: 1) recognition of the pattern when faced with range query problems; 2) correct implementation, especially regarding off-by-one errors and edge cases (empty array, single element, full array range); 3) ability to articulate the time and space complexity; and 4) creativity in extending the basic concept (e.g., using prefix sums with hash maps for 'subarray sum equals K' type problems, or applying it in a 2D context). It's a quick way to demonstrate analytical thinking and problem-solving fundamentals.

Key Takeaways

• Prefix Sum transforms O(N) range sum queries into O(1) queries after an O(N) precomputation.
• It uses O(N) auxiliary space to store cumulative sums.
• The core formula for sum A[left...right] is P[right+1] - P[left] (with P[0]=0).
• Beware of off-by-one errors and handle edge cases like left=0 correctly.
• A key building block for many medium-to-hard array problems.

Practice Problems

(See Practice Problems index below)