Prefix Sum Technique

The prefix sum technique (also known as a cumulative sum array) is a powerful method for optimizing range sum queries in arrays. Instead of recalculating sums repeatedly, we pre-process the array to answer queries in constant time.

Why Use the Prefix Sum Technique?

Imagine you run a small bakery and track daily sales in an array:

// Sales from Monday to Friday  
const dailySales = [10, 5, 20, 30, 15]; 

If a customer asks, "How many pastries were sold from Tuesday to Thursday?", you could manually sum 5 + 20 + 30 = 55. But what if you get hundreds of such queries? Recalculating each time is inefficient.

This is where the prefix sum array shines—it precomputes cumulative sums, allowing instant range sum calculations.

How Prefix Sum Works

Construct the Prefix Sum Array: Build prefix sum for entire array

function buildPrefixSum(arr: number[]): number[] {
    const prefixSum = new Array(arr.length);
    prefixSum[0] = arr[0];
    for (let i = 1; i < arr.length; i++) {
        prefixSum[i] = prefixSum[i - 1] + arr[i];
    }
    return prefixSum;
} 

Answer Range Queries in O(1) Time: To find the sum between indices L and R

function rangeSum(L: number, R: number, prefixSum: number[]): number {
    return prefixSum[R] - (L > 0 ? prefixSum[L - 1] : 0);
}

// Sales from Monday to Friday  
const dailySales = [10, 5, 20, 30, 15]; 

// Sales from Monday to Friday  
// [10, 15, 35, 65, 80] 
const prefixSum = buildPrefixSum(dailySales); 

// 55 (Tuesday to Thursday)  
console.log(rangeSum(1, 3, prefixSum)); 

Problem: Subarray Sum Equals K

Given an array of integers nums and an integer k, find the total number of continuous subarrays whose sum equals k. nums = [1, 2, 3], k = 3

We need to find all subarrays that sums to 3. Basically, we can use this equation sum(i, j) = k.

Solution Code:

function subarraySum(nums: number[], k: number): number {
    const prefixSumCount = new Map();

    let count = 0;
    let currentSum = 0;

    // Base case: sum 0 occurs once before start
    prefixSumCount.set(0, 1); 

    for (const num of nums) {
        currentSum += num;
        
        // Check if (currentSum - k) exists in the map
        if (prefixSumCount.has(currentSum - k)) {
            count += prefixSumCount.get(currentSum - k)!;
        }
        
        // Update the frequency of currentSum
        prefixSumCount.set(currentSum, (prefixSumCount.get(currentSum) || 0) + 1);
    }

    return count;
}

// Example Usage
console.log(subarraySum([1, 2, 3], 3)); // Output: 2

Time & Space Complexity:

Problem: Counting Subarrays with Sum Divisible by K

Given an array of integers nums and an integer k, return the number of non-empty subarrays where the sum of elements is divisible by k.

function subarraysDivByK(nums: number[], k: number): number {
    const remainderCount = new Map();

    let count = 0;
    let prefixSum = 0;

    // Base case: sum 0 (divisible by k)
    remainderCount.set(0, 1); 

    for (const num of nums) {
        prefixSum += num;

        // Handle negative remainders (e.g., -3 % 5 = 2)
        let remainder = ((prefixSum % k) + k) % k;

        // If remainder seen before, add its count to result
        if (remainderCount.has(remainder)) {
            count += remainderCount.get(remainder)!;
        }

        // Update remainder count
        remainderCount.set(remainder, (remainderCount.get(remainder) || 0) + 1);
    }

    return count;
}

// Output
// [4, 5, 0, -2, -3], 
// [5], 
// [5, 0], 
// [5, 0, -2, -3], 
// [0], 
// [0, -2, -3], 
// [-2, -3]
console.log(subarraysDivByK([4, 5, 0, -2, -3, 1], 5)); // Output: 7

Final Thoughts

The prefix sum technique is a must-know for coding interviews and performance-critical applications. By trading a small amount of extra space for O(1) range queries, it drastically improves efficiency.