Prefix Sum and Cumulative Techniques

1. Basic Prefix Sum Implementation

Concept	Formula	Query Time	Use Case
Prefix Sum Array	`prefix[i] = arr[0] + ... + arr[i]`	`O(1)`	Range sum queries after O(n) preprocessing
Range Sum Query	`sum[L,R] = prefix[R] - prefix[L-1]`	`O(1)`	Get sum of elements from index L to R
Cumulative Sum	`prefix[i] = prefix[i-1] + arr[i]`	`O(n)` build	Progressive sum accumulation
Zero Initialization	`prefix[0] = 0 or arr[0]`	N/A	Simplifies boundary handling

Example: Range sum query using prefix sum

class NumArray {
    constructor(nums) {
        this.prefix = new Array(nums.length + 1).fill(0);
        
        // Build prefix sum array
        for (let i = 0; i < nums.length; i++) {
            this.prefix[i + 1] = this.prefix[i] + nums[i];
        }
    }
    
    sumRange(left, right) {
        // Sum from left to right (inclusive)
        return this.prefix[right + 1] - this.prefix[left];
    }
}

// Example usage
const numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
console.log(numArray.sumRange(0, 2)); // Output: 1 (-2+0+3)
console.log(numArray.sumRange(2, 5)); // Output: -1 (3-5+2-1)

Example: Subarray sum equals k (prefix sum with HashMap)

function subarraySum(nums, k) {
    const prefixSumCount = new Map();
    prefixSumCount.set(0, 1); // Base case
    
    let sum = 0;
    let count = 0;
    
    for (let num of nums) {
        sum += num;
        
        // Check if (sum - k) exists
        if (prefixSumCount.has(sum - k)) {
            count += prefixSumCount.get(sum - k);
        }
        
        // Add current sum to map
        prefixSumCount.set(sum, (prefixSumCount.get(sum) || 0) + 1);
    }
    
    return count;
}

// Example: [1,1,1], k=2 -> Output: 2 ([1,1] appears twice)

2. 2D Prefix Sum for Matrix Queries

Operation	Formula	Complexity	Purpose
2D Prefix Build	`P[i][j] = P[i-1][j] + P[i][j-1] - P[i-1][j-1] + M[i][j]`	`O(m×n)`	Precompute cumulative sums for matrix
Rectangle Sum	`Sum = P[r2][c2] - P[r1-1][c2] - P[r2][c1-1] + P[r1-1][c1-1]`	`O(1)`	Query sum of submatrix in constant time
Inclusion-Exclusion	Add total, subtract overlaps, add back intersection	`O(1)`	Avoid double counting in 2D space
Padding Approach	Add extra row/column of zeros at index 0	Space: `O(m×n)`	Simplify boundary conditions

Example: 2D range sum query (immutable matrix)

class NumMatrix {
    constructor(matrix) {
        if (!matrix.length || !matrix[0].length) {
            this.prefix = [];
            return;
        }
        
        const m = matrix.length;
        const n = matrix[0].length;
        
        // Create prefix sum with padding
        this.prefix = Array(m + 1).fill(0)
            .map(() => Array(n + 1).fill(0));
        
        // Build 2D prefix sum
        for (let i = 1; i <= m; i++) {
            for (let j = 1; j <= n; j++) {
                this.prefix[i][j] = matrix[i-1][j-1]
                    + this.prefix[i-1][j]
                    + this.prefix[i][j-1]
                    - this.prefix[i-1][j-1];
            }
        }
    }
    
    sumRegion(row1, col1, row2, col2) {
        // Sum of rectangle from (row1,col1) to (row2,col2)
        return this.prefix[row2+1][col2+1]
            - this.prefix[row1][col2+1]
            - this.prefix[row2+1][col1]
            + this.prefix[row1][col1];
    }
}

3. Difference Array for Range Updates

Technique	Operation	Update Time	Application
Difference Array	`diff[i] = arr[i] - arr[i-1]`	`O(1)` per update	Efficient range increment/decrement
Range Update	`diff[L] += val; diff[R+1] -= val`	`O(1)`	Add value to range [L, R] efficiently
Reconstruct Array	`arr[i] = arr[i-1] + diff[i]`	`O(n)`	Build final array after all updates
Multiple Updates	Apply all updates, then reconstruct once	`O(k + n)`	k updates + n reconstruction

Example: Range addition using difference array

function getModifiedArray(length, updates) {
    const diff = new Array(length + 1).fill(0);
    
    // Apply all updates to difference array
    for (let [start, end, inc] of updates) {
        diff[start] += inc;
        diff[end + 1] -= inc;
    }
    
    // Reconstruct array using prefix sum
    const result = new Array(length);
    result[0] = diff[0];
    
    for (let i = 1; i < length; i++) {
        result[i] = result[i-1] + diff[i];
    }
    
    return result;
}

// Example: length=5, updates=[[1,3,2],[2,4,3],[0,2,-2]]
// Output: [-2,0,3,5,3]

Example: Corporate flight bookings

function corpFlightBookings(bookings, n) {
    const diff = new Array(n + 1).fill(0);
    
    // Each booking adds seats to a range of flights
    for (let [first, last, seats] of bookings) {
        diff[first - 1] += seats; // 1-indexed
        diff[last] -= seats;
    }
    
    // Build result array
    const result = new Array(n);
    result[0] = diff[0];
    
    for (let i = 1; i < n; i++) {
        result[i] = result[i-1] + diff[i];
    }
    
    return result;
}

4. Range Query Optimization

Strategy	Preprocessing	Query	Best For
Prefix Sum	`O(n)`	`O(1)`	Immutable arrays, frequent sum queries
Sparse Table	`O(n log n)`	`O(1)`	Range min/max queries, immutable data
Segment Tree	`O(n)`	`O(log n)`	Mutable arrays, range queries + updates
Fenwick Tree (BIT)	`O(n log n)`	`O(log n)`	Prefix sums with updates, space efficient

Immutable Range Queries

Query Type	Best Structure
Range Sum	Prefix Sum Array
Range Min/Max	Sparse Table
Range GCD	Sparse Table

Mutable Range Queries

Query Type	Best Structure
Point Update + Range Sum	Fenwick Tree
Range Update + Query	Segment Tree
Complex Aggregates	Segment Tree

Example: Product of array except self (prefix/suffix product)

function productExceptSelf(nums) {
    const n = nums.length;
    const result = new Array(n);
    
    // Build prefix products from left
    result[0] = 1;
    for (let i = 1; i < n; i++) {
        result[i] = result[i-1] * nums[i-1];
    }
    
    // Build suffix products from right and combine
    let suffixProduct = 1;
    for (let i = n - 1; i >= 0; i--) {
        result[i] *= suffixProduct;
        suffixProduct *= nums[i];
    }
    
    return result;
}

// [1,2,3,4] -> [24,12,8,6] (O(n) time, O(1) extra space)

5. Prefix XOR and Bitwise Operations

Operation	Property	Formula	Application
Prefix XOR	`a ^ a = 0`	`xor[i] = xor[i-1] ^ arr[i]`	Range XOR queries, finding unique elements
Range XOR	Self-inverse property	`xor[L,R] = xor[R] ^ xor[L-1]`	Cancel out common prefix
Single Number	XOR eliminates pairs	`result = a[0] ^ ... ^ a[n]`	Find element appearing odd times
Prefix OR/AND	Bitwise cumulation	Similar to prefix sum pattern	Aggregate bitwise operations

Example: XOR queries of a subarray

function xorQueries(arr, queries) {
    const n = arr.length;
    const prefixXor = new Array(n + 1).fill(0);
    
    // Build prefix XOR array
    for (let i = 0; i < n; i++) {
        prefixXor[i + 1] = prefixXor[i] ^ arr[i];
    }
    
    // Answer queries
    const result = [];
    for (let [left, right] of queries) {
        // XOR of range [left, right]
        result.push(prefixXor[right + 1] ^ prefixXor[left]);
    }
    
    return result;
}

// arr=[1,3,4,8], queries=[[0,1],[1,2],[0,3],[3,3]]
// Output: [2,7,14,8]

Example: Count triplets with XOR equal to zero

function countTriplets(arr) {
    const n = arr.length;
    let count = 0;
    
    // Build prefix XOR
    const prefixXor = new Array(n + 1).fill(0);
    for (let i = 0; i < n; i++) {
        prefixXor[i + 1] = prefixXor[i] ^ arr[i];
    }
    
    // If prefixXor[i] === prefixXor[j], 
    // XOR from i to j-1 is 0
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j <= n; j++) {
            if (prefixXor[i] === prefixXor[j]) {
                // All subarrays in [i, j-1] work
                count += j - i - 1;
            }
        }
    }
    
    return count;
}

6. Memory-efficient Prefix Calculations

Technique	Space Optimization	Trade-off	When to Use
Rolling Variables	`O(n) → O(1)`	Can only query current position	One-pass calculations, streaming data
In-place Modification	Reuse input array	Destroys original data	When input can be modified
On-demand Computation	No preprocessing storage	Higher query time	Few queries, large data
Compressed Storage	Store only key indices	More complex logic	Sparse arrays, many zeros

Example: Running sum with O(1) space

function runningSum(nums) {
    // Modify array in-place
    for (let i = 1; i < nums.length; i++) {
        nums[i] += nums[i - 1];
    }
    return nums; // O(1) extra space
}

// Alternative: Using separate accumulator
function runningSumConstantSpace(nums) {
    const result = new Array(nums.length);
    let sum = 0;
    
    for (let i = 0; i < nums.length; i++) {
        sum += nums[i];
        result[i] = sum;
    }
    
    return result;
}

Example: Max sum with rolling variables

function maxSubArray(nums) {
    // Kadane's algorithm - O(1) space
    let maxSoFar = nums[0];
    let maxEndingHere = nums[0];
    
    for (let i = 1; i < nums.length; i++) {
        // Extend or restart subarray
        maxEndingHere = Math.max(nums[i], maxEndingHere + nums[i]);
        maxSoFar = Math.max(maxSoFar, maxEndingHere);
    }
    
    return maxSoFar;
}

// No array storage needed - just two variables

Note: Prefix sum transforms O(n) range queries into O(1) queries with O(n) preprocessing. The difference array technique enables O(1) range updates instead of O(n), crucial for multiple update operations.

Prefix Sum Pattern Summary

1D Prefix: prefix[i] = prefix[i-1] + arr[i] for O(1) range sums
2D Prefix: Inclusion-exclusion principle for rectangle queries
Difference Array: Range updates in O(1), reconstruct in O(n)
XOR Prefix: Use XOR properties: a ^ a = 0, a ^ 0 = a
Space Optimization: Rolling variables for one-pass, in-place when allowed

Warning: When using 1-indexed arrays or padding with zeros, ensure consistent indexing in both construction and queries. For 2D prefix sums, be careful with the inclusion-exclusion formula - subtract both sides then add back the intersection to avoid double counting.

Related Cheatsheets

Datastructures-algorithms