Prefix Sum Pattern - (Theory)

Concept

Prefix sum is a technique that precomputes cumulative sums of an array, enabling efficient range sum queries. It transforms O(n) range queries into O(1) operations after O(n) precomputation.

Key Patterns

1. 1D Prefix Sum

   • Compute cumulative sums for linear arrays.
   • Use Case: Range sum queries on 1D arrays.

2. 2D Prefix Sum

   • Compute cumulative sums for matrices.
   • Use Case: Sum queries on rectangular submatrices.

3. Prefix Sum with Hash Map

   • Track frequency of prefix sums using a hash map.
   • Use Case: Count subarrays with a target sum (e.g., "Subarray Sum Equals K").

4. Circular Prefix Sum

   • Handle circular arrays by doubling the array or using modulo arithmetic.
   • Use Case: Range queries in circular arrays.

5. Difference Array

   • Inverse of prefix sum; enables efficient range updates.
   • Use Case: Range addition problems (e.g., "Range Addition").

Generic Templates

1. 1D Prefix Sum

class PrefixSum1D {
    private int[] prefix;

    // Precomputation: O(n)
    public PrefixSum1D(int[] arr) {
        int n = arr.length;
        prefix = new int[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + arr[i];
        }
    }

    // Query [l, r]: O(1)
    public int query(int l, int r) {
        return prefix[r + 1] - prefix[l];
    }
}

• TC: Precomputation O(n), Query O(1)
• SC: O(n)

2. 2D Prefix Sum

class PrefixSum2D {
    private int[][] prefix;

    // Precomputation: O(mn)
    public PrefixSum2D(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        prefix = new int[m + 1][n + 1];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                prefix[i + 1][j + 1] = matrix[i][j] + prefix[i][j + 1] 
                                      + prefix[i + 1][j] - prefix[i][j];
            }
        }
    }

    // Query [r1, c1] to [r2, c2]: O(1)
    public int query(int r1, int c1, int r2, int c2) {
        return prefix[r2 + 1][c2 + 1] - prefix[r1][c2 + 1] 
             - prefix[r2 + 1][c1] + prefix[r1][c1];
    }
}

• TC: Precomputation O(mn), Query O(1)
• SC: O(mn)

3. Prefix Sum with Hash Map (Subarray Sum Equals K)

public int subarraySum(int[] nums, int k) {
    Map<Integer, Integer> map = new HashMap<>();
    map.put(0, 1); // Base case: prefix sum 0
    int sum = 0, count = 0;
    
    for (int num : nums) {
        sum += num;
        // If (sum - k) exists, add its frequency
        count += map.getOrDefault(sum - k, 0);
        map.put(sum, map.getOrDefault(sum, 0) + 1);
    }
    return count;
}

• TC: O(n)
• SC: O(n)

4. Circular Prefix Sum

public int circularSubarraySum(int[] nums, int k) {
    int n = nums.length;
    int[] doubled = new int[2 * n];
    System.arraycopy(nums, 0, doubled, 0, n);
    System.arraycopy(nums, 0, doubled, n, n);
    
    PrefixSum1D ps = new PrefixSum1D(doubled);
    int count = 0;
    for (int i = 0; i < n; i++) {
        int sum = ps.query(i, i + k - 1);
        // Process sum for circular subarray
    }
    return count;
}

• TC: O(n)
• SC: O(n)

5. Difference Array (Range Updates)

class DifferenceArray {
    private int[] diff;

    // Initialize difference array: O(n)
    public DifferenceArray(int[] arr) {
        int n = arr.length;
        diff = new int[n + 1]; // Extra space for safety
        diff[0] = arr[0];
        for (int i = 1; i < n; i++) {
            diff[i] = arr[i] - arr[i - 1];
        }
    }

    // Range update [l, r] + val: O(1)
    public void rangeUpdate(int l, int r, int val) {
        diff[l] += val;
        if (r + 1 < diff.length) diff[r + 1] -= val;
    }

    // Convert diff array back to original: O(n)
    public int[] getArray() {
        int[] arr = new int[diff.length - 1];
        arr[0] = diff[0];
        for (int i = 1; i < arr.length; i++) {
            arr[i] = arr[i - 1] + diff[i];
        }
        return arr;
    }
}

• TC: Update O(1), Final retrieval O(n)
• SC: O(n)

When to Use Prefix Sum

• Range Sum Queries: Static arrays with frequent sum queries.
• Subarray Problems: "Subarray Sum Equals K", "Maximum Subarray".
• Matrix Sum Queries: Sum over arbitrary rectangles.
• Range Updates: Batched range additions (Difference Array).

Time & Space Complexity Summary

Prefix sum optimizes range-based operations by trading space for time, making it indispensable for efficient querying in competitive programming and interviews.