algorithms/docs/01-foundations/prefix-sums.md

Prefix Sum Pattern

Overview

Prefix sum is a powerful technique for efficiently answering range sum queries and solving various array problems. It involves precomputing cumulative sums to allow O(1) range queries.

Core Concepts

Prefix Sum Definition

The prefix sum array prefix is defined such that:

prefix[i] = arr[0] + arr[1] + ... + arr[i]

Given a range query from index i to j:

sum(i, j) = prefix[j] - prefix[i-1]

Basic Implementation

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

function rangeSum(prefix: number[], left: number, right: number): number {
    if (left === 0) {
        return prefix[right];
    }
    return prefix[right] - prefix[left-1];
}

Variations

1. Prefix Product

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

function rangeProduct(prefix: number[], left: number, right: number): number {
    if (left === 0) {
        return prefix[right];
    }
    return prefix[right] / prefix[left-1];
}

2. 2D Prefix Sum

function build2DPrefixSum(matrix: number[][]): number[][] {
    const rows = matrix.length;
    const cols = matrix[0].length;
    const prefix = Array.from({ length: rows + 1 }, () => Array(cols + 1).fill(0));
    
    for (let i = 1; i <= rows; i++) {
        for (let j = 1; j <= cols; j++) {
            prefix[i][j] = matrix[i-1][j-1] + 
                          prefix[i-1][j] + 
                          prefix[i][j-1] - 
                          prefix[i-1][j-1];
        }
    }
    
    return prefix;
}

function range2DSum(prefix: number[][], row1: number, col1: number, row2: number, col2: number): number {
    return prefix[row2+1][col2+1] - 
           prefix[row1][col2+1] - 
           prefix[row2+1][col1] + 
           prefix[row1][col1];
}

3. Prefix XOR

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

function rangeXOR(prefix: number[], left: number, right: number): number {
    if (left === 0) {
        return prefix[right];
    }
    return prefix[right] ^ prefix[left-1];
}

Applications

1. Subarray Sum Equals K

function subarraySum(nums: number[], k: number): number {
    const prefixSum = { 0: 1 };
    let currentSum = 0;
    let count = 0;
    
    for (const num of nums) {
        currentSum += num;
        
        // Check if there's a prefix that sums to currentSum - k
        if (prefixSum[currentSum - k]) {
            count += prefixSum[currentSum - k];
        }
        
        // Store current prefix sum
        prefixSum[currentSum] = (prefixSum[currentSum] || 0) + 1;
    }
    
    return count;
}

2. Find Maximum Subarray Sum

function maxSubArray(nums: number[]): number {
    let maxSum = nums[0];
    let currentSum = nums[0];
    
    for (let i = 1; i < nums.length; i++) {
        currentSum = Math.max(nums[i], currentSum + nums[i]);
        maxSum = Math.max(maxSum, currentSum);
    }
    
    return maxSum;
}

3. Product of Array Except Self

function productExceptSelf(nums: number[]): number[] {
    const n = nums.length;
    const left = new Array(n);
    const right = new Array(n);
    const result = new Array(n);
    
    // Left prefix products
    left[0] = 1;
    for (let i = 1; i < n; i++) {
        left[i] = left[i-1] * nums[i-1];
    }
    
    // Right prefix products
    right[n-1] = 1;
    for (let i = n-2; i >= 0; i--) {
        right[i] = right[i+1] * nums[i+1];
    }
    
    // Result is product of left and right
    for (let i = 0; i < n; i++) {
        result[i] = left[i] * right[i];
    }
    
    return result;
}

Time Complexity Analysis

Operation	Time Complexity	Space Complexity	Notes
Build Prefix Sum	O(n)	O(n)	One pass through array
Range Query	O(1)	O(1)	Constant time lookup
2D Prefix Sum	O(mn)	O(mn)	For m×n matrix
2D Range Query	O(1)	O(1)	Rectangle sum query

Best Practices

1. Handling Edge Cases

// Handle empty array
if (arr.length === 0) return [];

// Handle single element
if (arr.length === 1) return [arr[0]];

// Handle negative numbers
// Prefix sum works with negatives too

2. Space Optimization

// In-place prefix sum (if input can be modified)
for (let i = 1; i < arr.length; i++) {
    arr[i] += arr[i-1];
}

3. Multiple Prefix Arrays

// For different operations, build separate prefix arrays
const sumPrefix = buildPrefixSum(arr);
const xorPrefix = buildPrefixXOR(arr);

Common Mistakes

1. Index Errors

// Wrong: off-by-one error
prefix[i] = prefix[i] + arr[i]; // Should use i-1

// Correct: proper indexing
prefix[i] = prefix[i-1] + arr[i];

2. Range Query Errors

// Wrong: incorrect range calculation
sum = prefix[right] - prefix[left]; // Misses left element

// Correct: proper range calculation
sum = prefix[right] - prefix[left-1];

3. Integer Overflow

// Problem: Large numbers can cause overflow
// Solution: Use BigInt or modulo operation
const prefix = new Array(n).fill(BigInt(0));

4. Not Handling Negative Numbers

// Prefix sums work with negatives automatically
// No special handling needed

Practice Problems

Easy

• Range sum query
• Prefix sum array construction
• Sum of subarray
• Product of array except self
• Find pivot index

Medium

• Subarray sum equals K
• [ Maximum subarray (Kadane's algorithm)
• Contiguous array
• Find the shortest subarray
• Minimum size subarray sum

Hard

• Maximum sum circular subarray
• Subarray product less than K
• Find longest subarray with equal 0s and 1s
• 2D range sum queries
• Range sum query 2D (immutable)

Real-world Applications

1. Data Analysis: Time series analysis, moving averages
2. Image Processing: Integral images for fast feature computation
3. Database Queries: Range queries on indexed data
4. Game Development: Collision detection, spatial queries

Advanced Techniques

1. Dynamic Programming with Prefix Sums

function countSubarrays(arr: number[], target: number): number {
    const prefixMap = new Map<number, number>();
    prefixMap.set(0, 1);
    let currentSum = 0;
    let count = 0;
    
    for (let i = 0; i < arr.length; i++) {
        currentSum += arr[i];
        
        // Find how many times currentSum - target has occurred
        if (prefixMap.has(currentSum - target)) {
            count += prefixMap.get(currentSum - target);
        }
        
        // Update prefix map
        prefixMap.set(currentSum, (prefixMap.get(currentSum) || 0) + 1);
    }
    
    return count;
}

2. Sliding Window with Prefix Sums

function findMaxAverage(nums: number[], k: number): number {
    // Build prefix sum
    const prefix = new Array(nums.length);
    prefix[0] = nums[0];
    for (let i = 1; i < nums.length; i++) {
        prefix[i] = prefix[i-1] + nums[i];
    }
    
    let maxSum = prefix[k-1];
    for (let i = k; i < nums.length; i++) {
        const currentSum = prefix[i] - prefix[i-k];
        maxSum = Math.max(maxSum, currentSum);
    }
    
    return maxSum / k;
}

Tips for Mastery

1. Understand the Mathematics

• Prefix sum is cumulative addition
• Range queries use the inclusion-exclusion principle
• The technique works for any associative operation (sum, product, min, max)

2. Practice Different Operations

• Sum, product, XOR, min, max
• 1D and 2D applications
• Dynamic programming combinations

3. Optimize Space

• In-place modifications when possible
• Single pass algorithms
• Space-efficient data structures

4. Combine with Other Patterns

• Sliding window
• Binary search
• Hash tables for frequency counting

Next Steps

1. Master basic prefix sum construction and queries
2. Practice 1D and 2D applications
3. Learn to combine with dynamic programming
4. Apply to real-world problems

---

Key Takeaway: Prefix sum is a fundamental technique for range queries and subarray problems. It transforms O(n) range queries into O(1) operations with O(n) preprocessing time. Always consider prefix sums when dealing with range-based array problems.