Prefix Sum & Difference Array

1. Introduction: The Power of Precomputation

Imagine you run a retail store, and you record your daily revenue in a ledger. Your boss asks, "How much did we make between day 4 and day 12?" You count it up. Then they ask, "What about between day 7 and day 20?" You count again. If they ask a million questions, you are doing a massive amount of repetitive counting.

Instead, what if you kept a running total? Day 1 revenue, Day 1+2 revenue, Day 1+2+3 revenue, etc. If the boss asks for the revenue from Day 4 to Day 12, you simply take the running total up to Day 12 and subtract the running total up to Day 3. Boom—you get the answer instantly!

This is the Prefix Sum technique. It is a mathematical precomputation strategy used to answer "Range Queries" on arrays in $O(1)$ constant time, avoiding repetitive $O(N)$ traversals.

2. Core Concept: Prefix Sums and Difference Arrays

1D Prefix Sum

A Prefix Sum array P of an array A is defined such that P[i] is the sum of all elements from A[0] to A[i]. Mathematically: P[i] = P[i-1] + A[i]

Once we have P, the sum of elements in A from index L to index R (inclusive) is simply: $\text{Sum}(L, R) = P[R] - P[L - 1]$ (Note: If $L=0$, the sum is just $P[R]$.)

1D Difference Array (Range Updates)

What if, instead of querying, you want to update a range? E.g., "Add 100 to all elements from index L to R." A naive loop takes $O(N)$. A Difference Array D helps do this in $O(1)$.

• To add val to range [L, R], you do: D[L] += val and D[R + 1] -= val.
• When you calculate the prefix sum of D later, the +val starts at L and continues adding to every element, until the -val cancels it out exactly after R!

3. Beginner Code Example: Range Sum Queries

Problem Statement: (LeetCode 303) Given an integer array, handle multiple queries of the form: "Calculate the sum of elements from index left to right".

Brute Force (Suboptimal)

// For every query:
public int sumRangeBrute(int[] nums, int left, int right) {
    int sum = 0;
    for (int i = left; i <= right; i++) sum += nums[i];
    return sum;
}

• Time: $O(N)$ per query. If there are $Q$ queries, total time is $O(Q \times N)$. Too slow!

Optimal Prefix Sum Approach

public class NumArray {
    private int[] prefix;

    public NumArray(int[] nums) {
        // We create an array of size N + 1 to elegantly handle the L=0 edge case.
        // prefix[i] will store the sum of the first 'i' elements.
        prefix = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
    }
    
    public int sumRange(int left, int right) {
        // Sum from left to right is prefix[right + 1] - prefix[left]
        return prefix[right + 1] - prefix[left];
    }
}

Complexity Analysis:

• Time Complexity: $O(N)$ for initialization (constructor). $O(1)$ per query! Total time for $Q$ queries is $O(N + Q)$.
• Space Complexity: $O(N)$ to store the prefix sum array.

4. Intermediate Code Example: Difference Array (Range Addition)

Problem Statement: (LeetCode 370) You have an array of length $N$ initialized to zeros. You are given $Q$ updates of the form [start, end, inc], meaning add inc to all elements between start and end. Return the final array.

public class DifferenceArray {
    public static int[] getModifiedArray(int length, int[][] updates) {
        int[] diff = new int[length];
        
        // 1. Process all updates in O(1) per update
        for (int[] update : updates) {
            int start = update[0];
            int end = update[1];
            int inc = update[2];
            
            diff[start] += inc;
            if (end + 1 < length) {
                diff[end + 1] -= inc;
            }
        }
        
        // 2. Compute prefix sum to build the final array
        int[] result = new int[length];
        result[0] = diff[0];
        
        for (int i = 1; i < length; i++) {
            result[i] = result[i - 1] + diff[i];
        }
        
        return result;
    }
}

Complexity Analysis:

• Time Complexity: $O(Q + N)$. $O(Q)$ to process updates, $O(N)$ to compute the final array.
• Space Complexity: $O(N)$ for the difference array.

5. Advanced Code Example: 2D Prefix Sum

Problem Statement: (LeetCode 304) Given a 2D matrix, calculate the sum of elements inside a rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

The Math Insight: In 1D, Sum(L, R) = P[R] - P[L-1]. In 2D, calculating the prefix sum P[i][j] (sum of rectangle from (0,0) to (i,j)) requires Inclusion-Exclusion principle: P[i][j] = Matrix[i][j] + P[i-1][j] + P[i][j-1] - P[i-1][j-1] (we subtract the top-left area because it was added twice).

To query a specific rectangle: Sum = P[r2][c2] - P[r1-1][c2] - P[r2][c1-1] + P[r1-1][c1-1]

public class NumMatrix {
    private int[][] dp;

    public NumMatrix(int[][] matrix) {
        if (matrix.length == 0 || matrix[0].length == 0) return;
        
        // Pad with an extra row and column of 0s to avoid boundary checks
        dp = new int[matrix.length + 1][matrix[0].length + 1];
        
        for (int r = 0; r < matrix.length; r++) {
            for (int c = 0; c < matrix[0].length; c++) {
                // Inclusion-Exclusion Principle
                dp[r + 1][c + 1] = matrix[r][c] 
                                 + dp[r][c + 1] 
                                 + dp[r + 1][c] 
                                 - dp[r][c];
            }
        }
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        // Because of the +1 padding, row/col indices shift by 1
        return dp[row2 + 1][col2 + 1] 
             - dp[row1][col2 + 1] 
             - dp[row2 + 1][col1] 
             + dp[row1][col1];
    }
}

Complexity Analysis:

• Time Complexity: $O(M \times N)$ to initialize. $O(1)$ per query!
• Space Complexity: $O(M \times N)$ to store the 2D prefix sum table.

6. Common Mistakes Beginners Make

1. Off-By-One Errors (Indices)

   • The Mistake: Doing prefix[right] - prefix[left-1] without handling left == 0. It throws an ArrayIndexOutOfBoundsException.
   • The Fix: Create a prefix array of size N + 1, initialized with prefix[0] = 0. Then the query becomes prefix[right+1] - prefix[left], completely avoiding negative indices.

2. Integer Overflow

   • The Mistake: Using int for the prefix sum array when the original array contains large numbers.
   • Why it's wrong: The sum of large int values quickly exceeds the 32-bit integer limit (2,147,483,647), causing silent overflow to negative numbers.
   • The Fix: Use long[] for the prefix sum array.

3. Using Prefix Sum when Array Elements are Mutated

   • The Mistake: Updating the original array and expecting the Prefix Sum array to magically update.
   • Why it's wrong: Prefix arrays are static precomputations. If the underlying data changes, the entire $O(N)$ prefix array must be recalculated! (If you need both rapid updates and rapid range queries, you must use a Segment Tree or Fenwick Tree).

7. Interview Q&A

Q1: How do you know when to use Prefix Sum in an interview? Answer: Any problem that asks for "sum of a subarray", "average of a range", or involves counting occurrences within a specific contiguous block across multiple queries is a massive red flag pointing toward Prefix Sum.

Q2: (LeetCode 560) Subarray Sum Equals K: Can we use the Prefix Sum technique to find how many subarrays sum to $K$ in $O(N)$ time? Answer: Yes! But not just by using the array. We use a HashMap. We keep a running prefix sum. At each step i, we check if current_sum - K exists in our HashMap of seen prefix sums. If it does, we know there is a subarray ending at i that sums to $K$. This reduces the time from $O(N^2)$ to $O(N)$.

Q3: What is the fundamental difference between a Sliding Window and Prefix Sum? Answer: Sliding window is used to find an optimal subarray (e.g., longest, shortest) based on a condition, often requiring elements to be positive. Prefix Sum is used to answer queries about specific subarrays or to mathematically calculate sums, and works perfectly fine with negative numbers.

Q4: Can we use Prefix Sum for operations other than Addition? Answer: Yes, but only for operations that have an inverse. Multiplication works (using division as inverse), XOR works (XOR is its own inverse). MAX and MIN do not work because you cannot "subtract" a max value to revert to a previous state. (For range MIN/MAX, use a Segment Tree or Sparse Table).

8. Practice Problems

1. Range Sum Query - Immutable (LeetCode 303)
   • Goal: Implement the standard 1D prefix sum class.
2. Subarray Sum Equals K (LeetCode 560)
   • Hint: Combine Prefix Sum with a HashMap to track frequencies of seen sums.
3. Corporate Flight Bookings (LeetCode 1109)
   • Hint: This is a classic Difference Array problem. Apply range updates and compute the prefix sum at the end.

9. Summary

• Prefix Sum: Transforms $O(N)$ range queries into $O(1)$ queries through $O(N)$ precomputation.
• Padding: Always create prefix arrays of size $N+1$ to elegantly bypass index-out-of-bounds errors on $0$-index queries.
• Difference Arrays: The reverse of Prefix Sums. Used to execute $O(1)$ range additions/updates, processing them all at the end with a single pass.
• 2D Prefix: Uses the Inclusion-Exclusion principle. Add the top, add the left, subtract the top-left intersection, and add the current cell.