When it comes to optimizing range queries and speeding up subarray calculations, Prefix Sum is one of the most efficient and widely used techniques. Whether you’re solving problems on arrays, matrices, or strings — this concept can simplify things drastically.

Let’s dive into the idea of prefix sum with Java code, intuition, and interview-level examples.

🔍 What is a Prefix Sum?

A Prefix Sum is a running total of values in an array. It allows you to compute the sum of any subarray in constant time after a linear-time preprocessing step.

🧠 Formula

For an array arr[], the prefix sum array prefix[] is defined as:

prefix[i] = prefix[i - 1] + arr[i]

To get the sum of elements from index l to r:

sum = prefix[r] - prefix[l - 1]

(Take care of index 0 edge case!)

🧪 Java Implementation

✅ Basic Prefix Sum of Array 

public int[] computePrefixSum(int[] arr) {
    int[] prefix = new int[arr.length];
    prefix[0] = arr[0];

    for (int i = 1; i < arr.length; i++) {
        prefix[i] = prefix[i - 1] + arr[i];
    }
    return prefix;
}

📘 Example 1: Range Sum Query (Immutable)

🔧 Problem:

Preprocess the array so you can get the sum of any subarray [i...j] in O(1) time.

public class RangeSumQuery {
    int[] prefix;

    public RangeSumQuery(int[] nums) {
        prefix = new int[nums.length];
        prefix[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            prefix[i] = prefix[i - 1] + nums[i];
        }
    }

    public int sumRange(int i, int j) {
        return i == 0 ? prefix[j] : prefix[j] - prefix[i - 1];
    }
}

📘 Example 2: Check Subarray Sum Equals K

🔧 Problem:

Count the number of subarrays with sum = K.

public int subarraySum(int[] nums, int k) {
    Map<Integer, Integer> map = new HashMap<>();
    map.put(0, 1);
    int count = 0, sum = 0;

    for (int num : nums) {
        sum += num;
        if (map.containsKey(sum - k)) {
            count += map.get(sum - k);
        }
        map.put(sum, map.getOrDefault(sum, 0) + 1);
    }
    return count;
}

🧠 This uses prefix sum + hashmap for efficient counting.

📘 Example 3: 2D Prefix Sum (Matrix)

🔧 Problem:

Efficiently compute the sum of a submatrix in a 2D grid.

public class NumMatrix {
    int[][] prefix;

    public NumMatrix(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 + 1][j] 
                    + prefix[i][j + 1] 
                    - prefix[i][j];
            }
        }
    }

    public int sumRegion(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];
    }
}

📘 Example 4: Maximum Sum Subarray (Kadane’s Algorithm vs. Prefix Sum)

You can use prefix sum to brute-force all subarrays:

public int maxSubarraySum(int[] nums) {
    int max = Integer.MIN_VALUE;
    int[] prefix = new int[nums.length];
    prefix[0] = nums[0];

    for (int i = 1; i < nums.length; i++) {
        prefix[i] = prefix[i - 1] + nums[i];
    }

    for (int i = 0; i < nums.length; i++) {
        for (int j = i; j < nums.length; j++) {
            int sum = i == 0 ? prefix[j] : prefix[j] - prefix[i - 1];
            max = Math.max(max, sum);
        }
    }
    return max;
}

⏱ Time: O(n²) — can be improved to O(n) using Kadane's Algorithm.

📘 Example 5: Binary String with Equal 0s and 1s

Convert '0' to -1 and use prefix sum to find longest balanced subarray.

public int findMaxLength(int[] nums) {
    Map<Integer, Integer> map = new HashMap<>();
    map.put(0, -1);
    int max = 0, sum = 0;

    for (int i = 0; i < nums.length; i++) {
        sum += (nums[i] == 0) ? -1 : 1;
        if (map.containsKey(sum)) {
            max = Math.max(max, i - map.get(sum));
        } else {
            map.put(sum, i);
        }
    }
    return max;
}

✅ Real-World Use Cases

  • Subarray sum problems
  • Histogram and matrix-based queries
  • Financial transactions or running totals
  • Game score calculations
  • Frequency and cumulative distributions

🎯 Key Takeaways

Concept Usage
1D Prefix Sum Quick range queries
2D Prefix Sum Matrix-based region queries
HashMap + Prefix Sum Count subarrays efficiently
Preprocessing O(n), then O(1) for queries

🚀 Final Tip

Prefix sum is a must-know technique — simple to implement, yet powerful in optimizing brute-force range queries into efficient solutions.