Prefix Sum

What is Prefix Sum?

A Prefix Sum array precomputes cumulative sums, allowing O(1) range sum queries after O(n) preprocessing.

Key Formula

For array arr[0..n-1], prefix sum prefix[i] = sum of elements from 0 to i:

prefix[0] = arr[0]
prefix[i] = prefix[i-1] + arr[i] for i > 0

Range sum [l, r] = prefix[r] - (l > 0 ? prefix[l-1] : 0)

Example

arr = [3, 1, 4, 2, 5]
prefix = [3, 4, 8, 10, 15]

Sum [1,3] = prefix[3] - prefix[0] = 10 - 3 = 7 (1+4+2)
Sum [2,4] = prefix[4] - prefix[1] = 15 - 4 = 11 (4+2+5)

Implementation

public class PrefixSum {
    private int[] prefix;
    private int[] arr;
    
    public PrefixSum(int[] nums) {
        arr = nums;
        int n = nums.length;
        prefix = new int[n];
        prefix[0] = nums[0];
        for (int i = 1; i < n; i++) {
            prefix[i] = prefix[i - 1] + nums[i];
        }
    }
    
    // Range sum [l, r] inclusive (0-indexed)
    public int rangeSum(int l, int r) {
        if (l == 0) return prefix[r];
        return prefix[r] - prefix[l - 1];
    }
    
    // Get prefix sum at index i
    public int getPrefixSum(int i) {
        return prefix[i];
    }
}

2D Prefix Sum

For matrix range sum queries:

public class PrefixSum2D {
    private int[][] prefix;
    private int m, n;
    
    public PrefixSum2D(int[][] matrix) {
        m = matrix.length;
        n = matrix[0].length;
        prefix = new int[m + 1][n + 1];
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                prefix[i][j] = matrix[i-1][j-1]
                    + prefix[i-1][j] + prefix[i][j-1]
                    - prefix[i-1][j-1];
            }
        }
    }
    
    // Sum of submatrix from (r1,c1) to (r2,c2) (0-indexed)
    public int rangeSum(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];
    }
}

Time Complexity

• Build: O(n) for 1D, O(mn) for 2D
• Query: O(1)
• Space: O(n) for 1D, O(mn) for 2D

Prefix Sum + Hash Map

Combining prefix sums with hash maps enables efficient subarray problems.

Subarray Sum Equals K

public int subarraySum(int[] nums, int k) {
    Map<Integer, Integer> prefixCount = new HashMap<>();
    prefixCount.put(0, 1);
    
    int prefixSum = 0;
    int count = 0;
    
    for (int num : nums) {
        prefixSum += num;
        
        // If (prefixSum - k) exists, we found subarrays summing to k
        if (prefixCount.containsKey(prefixSum - k)) {
            count += prefixCount.get(prefixSum - k);
        }
        
        prefixCount.put(prefixSum, prefixCount.getOrDefault(prefixSum, 0) + 1);
    }
    
    return count;
}

Find Pivot Index

public int pivotIndex(int[] nums) {
    int totalSum = 0;
    for (int num : nums) totalSum += num;
    
    int leftSum = 0;
    for (int i = 0; i < nums.length; i++) {
        if (leftSum == totalSum - leftSum - nums[i]) {
            return i;
        }
        leftSum += nums[i];
    }
    
    return -1;
}

Contiguous Array (Equal 0s and 1s)

public int findMaxLength(int[] nums) {
    Map<Integer, Integer> prefixMap = new HashMap<>();
    prefixMap.put(0, -1);
    
    int prefixSum = 0;
    int maxLen = 0;
    
    for (int i = 0; i < nums.length; i++) {
        prefixSum += (nums[i] == 1) ? 1 : -1;
        
        if (prefixMap.containsKey(prefixSum)) {
            maxLen = Math.max(maxLen, i - prefixMap.get(prefixSum));
        } else {
            prefixMap.put(prefixSum, i);
        }
    }
    
    return maxLen;
}

Product of Array Except Self (Prefix Product)

public int[] productExceptSelf(int[] nums) {
    int n = nums.length;
    int[] result = new int[n];
    
    // Left products
    result[0] = 1;
    for (int i = 1; i < n; i++) {
        result[i] = result[i - 1] * nums[i - 1];
    }
    
    // Right products
    int rightProduct = 1;
    for (int i = n - 1; i >= 0; i--) {
        result[i] *= rightProduct;
        rightProduct *= nums[i];
    }
    
    return result;
}