Data Structures & AlgorithmsCommon Array Patterns & Problem Types

Common Array Patterns & Problem Types

LevelIntermediate

Duration90 mins

TopicCommon Array Patterns & Problem Types

1 / 5

Prefix Sums and Cumulative Arrays

The Power of Precomputation

Imagine you're building a financial dashboard that must answer thousands of queries per second: "What was the total revenue between March 15th and June 22nd?" or "How much did we spend in Q3?" Each query asks for the sum of values within a range of your data.

The naive approach—iterating through the range and adding up values for each query—works fine for occasional questions. But at scale, with millions of data points and thousands of concurrent queries, this approach becomes a performance bottleneck that can bring your system to its knees.

Enter prefix sums, one of the most elegant and universally applicable array patterns in computer science. This technique transforms O(n) range sum queries into O(1) operations through the strategic investment of upfront computation. It's a masterclass in the fundamental algorithmic principle of trading preprocessing time for query efficiency.

What You Will Master

By the end of this page, you will deeply understand prefix sums: their mathematical foundation, construction algorithms, constant-time range queries, space-time tradeoffs, variations (difference arrays, 2D prefix sums), and practical applications from competitive programming to production systems.

The Problem: Repeated Range Queries

Let's formalize the problem that prefix sums solve. Given an array of n elements, we want to efficiently answer multiple queries of the form:

Range Sum Query: "What is the sum of elements from index i to index j (inclusive)?"

This seemingly simple question appears constantly in real-world applications:

Range Query Applications

•Financial analytics — Total sales between two dates, cumulative P&L, running balances
•Time-series databases — Aggregate sensor readings over intervals
•Image processing — Summed area tables for fast region-based calculations
•Game development — Damage calculations, score accumulation, area-of-effect computations
•Network analysis — Bandwidth usage over time windows, packet counts
•Competitive programming — Countless problems reduce to range sum queries

The Naive Approach and Its Limitations

The straightforward solution iterates through the specified range and accumulates the sum:

naiveRangeSum.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// Naive range sum: O(n) per query
function rangeSum(arr: number[], left: number, right: number): number {
    let sum = 0;
    for (let i = left; i <= right; i++) {
        sum += arr[i];
    }
    return sum;
}
 
// Example usage
const data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3];
 
// Query: Sum from index 2 to 7 (inclusive)
const result = rangeSum(data, 2, 7);
console.log(result); // 4 + 1 + 5 + 9 + 2 + 6 = 27

Complexity Analysis of the Naive Approach:

Time per query: O(k), where k = right - left + 1
Worst case: O(n) when querying the entire array
For Q queries: O(Q × n) total time

This might seem acceptable, but consider the scale implications:

Naive Range Sum Query Performance at Scale
Array Size (n)	Queries (Q)	Operations	At 1B ops/sec
1,000	1,000	1 million	1 millisecond
100,000	10,000	1 billion	1 second
1,000,000	100,000	100 billion	100 seconds
10,000,000	1,000,000	10 trillion	~3 hours

The Scale Cliff

What works in development fails in production. A million queries against a million-element array takes over an hour with the naive approach. Interactive systems become unresponsive. Batch jobs miss their windows. This is precisely where prefix sums shine.

The Insight: Cumulative Sums and Telescoping

The breakthrough behind prefix sums comes from a simple mathematical observation. Consider what happens when we compute cumulative sums from the beginning of an array:

For an array A = [a₀, a₁, a₂, a₃, ..., aₙ₋₁], we define the prefix sum array P where:

P[0] = 0 (empty sum, a sentinel value)
P[1] = a₀
P[2] = a₀ + a₁
P[3] = a₀ + a₁ + a₂
...
P[k] = a₀ + a₁ + ... + aₖ₋₁ (sum of first k elements)

The key insight is this: any contiguous range sum can be expressed as the difference of two prefix sums.

The Telescoping Principle

Sum(i to j) = P[j+1] - P[i]

This works because P[j+1] contains the sum from index 0 to j, and P[i] contains the sum from index 0 to i-1. Subtracting cancels all elements before index i, leaving exactly the sum from i to j.

Visual Proof:

Let's trace through this with a concrete example:

Original array A:     [3, 1, 4, 1, 5, 9, 2, 6]
Indices:               0  1  2  3  4  5  6  7

Prefix sum array P:   [0, 3, 4, 8, 9, 14, 23, 25, 31]
Indices:               0  1  2  3  4   5   6   7   8

Query: Sum from index 2 to 5 (inclusive)

Direct calculation: A[2] + A[3] + A[4] + A[5] = 4 + 1 + 5 + 9 = 19
Using prefix sums: P[6] - P[2] = 23 - 4 = 19 ✓

Why does this work?

P[6] = A[0] + A[1] + A[2] + A[3] + A[4] + A[5] = 3 + 1 + 4 + 1 + 5 + 9 = 23
P[2] = A[0] + A[1]                             = 3 + 1             = 4

P[6] - P[2] = (A[0] + A[1] + A[2] + A[3] + A[4] + A[5]) - (A[0] + A[1])
            = A[2] + A[3] + A[4] + A[5]
            = 19

The subtraction telescopes, canceling all terms before our desired range. This is the elegant heart of the prefix sum technique.

Zero-Indexed Prefix Array Convention

We use P of size n+1 with P[0] = 0 as a sentinel. This handles edge cases elegantly: querying from index 0 just becomes P[right+1] - P[0] = P[right+1] - 0 = P[right+1]. No special-case logic needed.

Building the Prefix Sum Array

Constructing the prefix sum array is a single O(n) pass. Each element is simply the sum of the previous prefix sum and the current original element. This recurrence relation makes the algorithm both simple and efficient:

prefixSumConstruction.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * Build a prefix sum array from the original array.
 * 
 * Time Complexity: O(n) — single pass through the array
 * Space Complexity: O(n) — new array of size n+1
 * 
 * @param arr The original array of numbers
 * @returns Prefix sum array where prefix[i] = sum of arr[0..i-1]
 */
function buildPrefixSum(arr: number[]): number[] {
    const n = arr.length;
    const prefix = new Array(n + 1).fill(0);
    
    // prefix[0] = 0 (sentinel for empty range)
    for (let i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + arr[i];
    }
    
    return prefix;
}
 
// Example
const data = [3, 1, 4, 1, 5, 9, 2, 6];
const prefixSums = buildPrefixSum(data);
 
console.log("Original:", data);
// [3, 1, 4, 1, 5, 9, 2, 6]
 
console.log("Prefix Sums:", prefixSums);
// [0, 3, 4, 8, 9, 14, 23, 25, 31]

Understanding the Recurrence:

The construction follows a simple recurrence relation:

P[0] = 0
P[i] = P[i-1] + A[i-1]   for i = 1, 2, ..., n

This is equivalent to:

P[i] = Σ(k=0 to i-1) A[k]

Each prefix sum builds upon the previous one, adding exactly one new element. This incremental construction is key to the O(n) time complexity.

Memory Optimization: In-Place Prefix Sums

If you don't need the original array afterward, you can compute prefix sums in-place, using no extra space. Simply overwrite each element with its running sum. However, this destroys the original data, so use this optimization only when appropriate.

inPlacePrefixSum.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * In-place prefix sum transformation.
 * Modifies the array to contain cumulative sums.
 * 
 * After transformation: arr[i] = sum of original arr[0..i]
 * 
 * Time: O(n), Space: O(1) auxiliary
 */
function prefixSumInPlace(arr: number[]): void {
    for (let i = 1; i < arr.length; i++) {
        arr[i] += arr[i - 1];
    }
}
 
// Example
const data = [3, 1, 4, 1, 5, 9, 2, 6];
prefixSumInPlace(data);
console.log(data);
// [3, 4, 8, 9, 14, 23, 25, 31]
 
// Note: Range query adjustment needed since no sentinel at index 0
// Sum(i to j) = arr[j] - arr[i-1] (handle i=0 specially)

Answering Range Queries in O(1)

With the prefix sum array constructed, any range sum query becomes a simple subtraction—two array accesses and one arithmetic operation:

rangeSumQuery.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Answer a range sum query in O(1) time using prefix sums.
 * 
 * @param prefix The precomputed prefix sum array (size n+1)
 * @param left Starting index of the range (inclusive)
 * @param right Ending index of the range (inclusive)
 * @returns Sum of elements from index left to right
 */
function rangeSum(prefix: number[], left: number, right: number): number {
    return prefix[right + 1] - prefix[left];
}
 
// Complete example
const data = [3, 1, 4, 1, 5, 9, 2, 6];
const prefix = buildPrefixSum(data);
 
// Various range queries — all O(1)
console.log(rangeSum(prefix, 0, 7));  // Entire array: 31
console.log(rangeSum(prefix, 2, 5));  // Indices 2-5: 19
console.log(rangeSum(prefix, 0, 0));  // Single element: 3
console.log(rangeSum(prefix, 4, 7));  // Indices 4-7: 22
console.log(rangeSum(prefix, 3, 3));  // Single element: 1

Complexity Comparison:

Naive vs Prefix Sum: Complexity Analysis
Metric	Naive Approach	Prefix Sum Approach
Preprocessing Time	O(1) (none)	O(n)
Preprocessing Space	O(1)	O(n)
Query Time	O(n) worst case	O(1)
Total for Q Queries	O(Q × n)	O(n + Q)
Update Original Array	O(1)	O(n) to rebuild

The Crossover Point

Prefix sums become advantageous when Q > 1 (more than one query). The break-even point is: O(n + Q) < O(Q × n), which simplifies to Q > n/(n-1) ≈ 1 for large n. In practice, even 2-3 queries justify the preprocessing for large arrays.

Handling Edge Cases:

Robust prefix sum implementations must handle several edge cases:

Empty array: Return empty prefix array or handle as error
Single element: Works naturally (P = [0, a₀])
Full array query: P[n] - P[0] = P[n]
Single element query (i=j): P[i+1] - P[i] = A[i] ✓
Invalid indices: Validate left ≤ right and bounds before querying

robustPrefixSum.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/**
 * A complete, production-ready prefix sum implementation
 * with proper validation and error handling.
 */
class PrefixSumArray {
    private prefix: number[];
    private n: number;
    
    constructor(arr: number[]) {
        this.n = arr.length;
        this.prefix = new Array(this.n + 1).fill(0);
        
        for (let i = 0; i < this.n; i++) {
            this.prefix[i + 1] = this.prefix[i] + arr[i];
        }
    }
    
    /**
     * Query the sum of elements in range [left, right] inclusive.
     * @throws Error if indices are out of bounds or invalid
     */
    rangeSum(left: number, right: number): number {
        // Validate indices
        if (left < 0 || right >= this.n) {
            throw new Error(`Index out of bounds: [0, ${this.n - 1}]`);
        }
        if (left > right) {
            throw new Error(`Invalid range: left (${left}) > right (${right})`);
        }
        
        return this.prefix[right + 1] - this.prefix[left];
    }
    
    /**
     * Get the total sum of all elements.
     */
    totalSum(): number {
        return this.prefix[this.n];
    }
    
    /**
     * Get the sum of the first k elements.
     */
    sumFirst(k: number): number {
        if (k < 0 || k > this.n) {
            throw new Error(`k must be in range [0, ${this.n}]`);
        }
        return this.prefix[k];
    }
}

The Space-Time Tradeoff

Prefix sums exemplify a fundamental principle in algorithm design: trading space for time (or equivalently, trading preprocessing for query efficiency).

This tradeoff appears throughout computer science:

Caching: Store computed results to avoid recomputation
Indexing: Build lookup structures to accelerate searches
Memoization: Remember subproblem solutions in dynamic programming
Precomputation tables: Store factorials, powers, combinatorics

Prefix sums represent perhaps the simplest and cleanest example of this tradeoff in action.

What We Pay (Costs)

•O(n) extra space for the prefix array
•O(n) preprocessing time upfront
•O(n) update cost if source data changes
•Memory bandwidth for cache misses on large arrays

What We Gain (Benefits)

•O(1) query time regardless of range size
•O(n + Q) total for Q queries vs O(nQ)
•Simple implementation with low constant factors
•Predictable performance — no worst-case spikes

When Prefix Sums Excel:

Query-heavy workloads: Many queries on static or slowly-changing data
Interactive applications: Real-time analytics, dashboards, games
Batch processing: Answering thousands of range queries in one pass
Competitive programming: Almost always beneficial when range sums appear

When to Reconsider:

Frequent updates: If the source array changes often, rebuilding the prefix array becomes expensive. Consider segment trees or Fenwick trees for O(log n) updates.
Single query: For literally one query, preprocessing isn't worth it.
Memory-constrained environments: When O(n) extra space is prohibitive.
Streaming data: When you can't store the full array anyway.

Dynamic Range Sum Structures

When you need both efficient queries AND efficient updates, prefix sums alone aren't enough. Fenwick Trees (Binary Indexed Trees) offer O(log n) for both operations. Segment Trees offer the same complexity with more flexibility for non-associative operations. These are covered in later modules.

Variation: Difference Arrays for Range Updates

Prefix sums have a powerful dual: the difference array. While prefix sums accelerate range queries, difference arrays accelerate range updates.

The Problem:

Given an array, perform multiple operations of the form:

"Add value v to all elements from index i to j"

Then, reconstruct the final array.

With the naive approach, each range update takes O(k) time where k is the range size. For Q updates: O(Q × n) total.

The Difference Array Solution:

For array A, define difference array D where:

D[0] = A[0]
D[i] = A[i] - A[i-1] for i > 0

The key insight: A range update [i, j] by value v becomes just two point updates in D:

D[i] += v (starting the increment)
D[j+1] -= v (ending the increment)

differenceArray.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/**
 * Difference Array for efficient range updates.
 * 
 * The difference array D encodes the "jumps" between consecutive elements.
 * A range update becomes two point operations.
 * The final array is recovered by computing prefix sums of D.
 */
class DifferenceArray {
    private diff: number[];
    private n: number;
    
    constructor(arr: number[]) {
        this.n = arr.length;
        this.diff = new Array(this.n + 1).fill(0);
        
        // Build difference array
        this.diff[0] = arr[0];
        for (let i = 1; i < this.n; i++) {
            this.diff[i] = arr[i] - arr[i - 1];
        }
    }
    
    /**
     * Add value to all elements in range [left, right] inclusive.
     * Time: O(1)
     */
    rangeUpdate(left: number, right: number, value: number): void {
        this.diff[left] += value;
        if (right + 1 < this.n) {
            this.diff[right + 1] -= value;
        }
    }
    
    /**
     * Reconstruct the final array after all updates.
     * Time: O(n) — essentially computing prefix sums
     */
    getResult(): number[] {
        const result = new Array(this.n);
        result[0] = this.diff[0];
        
        for (let i = 1; i < this.n; i++) {
            result[i] = result[i - 1] + this.diff[i];
        }
        
        return result;
    }
}
 
// Example: Apply multiple range updates
const initial = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0];
const da = new DifferenceArray(initial);
 
da.rangeUpdate(2, 5, 10);   // Add 10 to indices 2-5
da.rangeUpdate(3, 8, 5);    // Add 5 to indices 3-8
da.rangeUpdate(0, 4, -3);   // Subtract 3 from indices 0-4
 
console.log(da.getResult());
// [-3, -3, 7, 12, 12, 15, 5, 5, 5, 0]

The Beautiful Duality

Prefix sums and difference arrays are mathematical inverses. Computing prefix sums from a difference array recovers the original array. Computing differences from a prefix sum array recovers the original array. This duality is fundamental to understanding both techniques.

Prefix Sum vs Difference Array
Technique	Fast Operation	Slow Operation	Primary Use
Prefix Sum	Range Query O(1)	Point Update O(n)	Many queries, few updates
Difference Array	Range Update O(1)	Point Query O(n)	Many updates, few queries

Extension: 2D Prefix Sums (Summed Area Tables)

The prefix sum concept extends naturally to two dimensions, creating what are known as 2D prefix sums or summed area tables (a term from image processing).

The Problem:

Given a 2D matrix of values, answer queries of the form:

"What is the sum of all elements in the rectangular region from (r1, c1) to (r2, c2)?"

The 2D Prefix Sum Construction:

For matrix M, build prefix sum matrix P where P[i][j] = sum of all elements in the rectangle from (0,0) to (i-1, j-1).

The construction uses the inclusion-exclusion principle:

P[i][j] = M[i-1][j-1] + P[i-1][j] + P[i][j-1] - P[i-1][j-1]

Add the cell above
Add the cell to the left
Subtract the diagonal (counted twice)
Add the current matrix element

twoDPrefixSum.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
/**
 * 2D Prefix Sum (Summed Area Table) for O(1) rectangular region sum queries.
 */
class PrefixSum2D {
    private prefix: number[][];
    private rows: number;
    private cols: number;
    
    constructor(matrix: number[][]) {
        if (matrix.length === 0 || matrix[0].length === 0) {
            this.rows = 0;
            this.cols = 0;
            this.prefix = [];
            return;
        }
        
        this.rows = matrix.length;
        this.cols = matrix[0].length;
        
        // Create prefix sum matrix with sentinel row and column
        this.prefix = Array.from(
            { length: this.rows + 1 },
            () => new Array(this.cols + 1).fill(0)
        );
        
        // Build using inclusion-exclusion
        for (let i = 1; i <= this.rows; i++) {
            for (let j = 1; j <= this.cols; 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];
            }
        }
    }
    
    /**
     * Query sum of rectangular region from (r1,c1) to (r2,c2) inclusive.
     * Uses inclusion-exclusion to compute in O(1).
     */
    regionSum(r1: number, c1: number, r2: number, c2: number): number {
        // Convert to 1-indexed prefix array coordinates
        r1++; c1++; r2++; c2++;
        
        return this.prefix[r2][c2]
            - this.prefix[r1 - 1][c2]
            - this.prefix[r2][c1 - 1]
            + this.prefix[r1 - 1][c1 - 1];
    }
}
 
// Example
const matrix = [
    [1, 2, 3, 4],
    [5, 6, 7, 8],
    [9, 10, 11, 12]
];
 
const ps2d = new PrefixSum2D(matrix);
 
// Sum of entire matrix
console.log(ps2d.regionSum(0, 0, 2, 3)); // 78
 
// Sum of middle 2x2 region (rows 0-1, cols 1-2)
console.log(ps2d.regionSum(0, 1, 1, 2)); // 2+3+6+7 = 18

Image Processing Origins

Summed area tables were introduced in computer graphics for fast texture mapping. They're used extensively in image processing for features like box blur, where you need to average pixels in a rectangular region. The Viola-Jones face detection algorithm famously uses integral images (another name for 2D prefix sums) to compute Haar-like features in constant time.

Complexity Analysis:

Preprocessing: O(m × n) time and space for an m × n matrix
Query: O(1) per rectangular region query
Extension: The technique generalizes to N dimensions with O(2^N) terms in the inclusion-exclusion formula, though practical use beyond 3D is rare.

Classic Problems Using Prefix Sums

Prefix sums unlock efficient solutions to a wide variety of problems. Here are several classics that every serious programmer should know:

Problem 1: Count Subarrays with Given Sum

•Problem: Count how many contiguous subarrays have sum equal to k.
•Insight: If prefixSum[j] - prefixSum[i] = k, then subarray [i, j-1] has sum k.
•Solution: Use a hash map to count prefix sum occurrences. For each new prefix sum, check how many previous prefix sums equal (current - k).
•Complexity: O(n) time, O(n) space.

subarraySum.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * Count subarrays with sum equal to k.
 * Uses prefix sums + hash map for O(n) solution.
 */
function subarraySum(nums: number[], k: number): number {
    const prefixCount = new Map<number, number>();
    prefixCount.set(0, 1); // Empty prefix has sum 0
    
    let count = 0;
    let currentSum = 0;
    
    for (const num of nums) {
        currentSum += num;
        
        // How many previous prefix sums equal (currentSum - k)?
        const target = currentSum - k;
        if (prefixCount.has(target)) {
            count += prefixCount.get(target)!;
        }
        
        // Record this prefix sum
        prefixCount.set(currentSum, (prefixCount.get(currentSum) || 0) + 1);
    }
    
    return count;
}
 
console.log(subarraySum([1, 1, 1], 2)); // 2
console.log(subarraySum([1, 2, 3], 3)); // 2

Problem 2: Subarray Divisibility

•Problem: Count subarrays whose sum is divisible by k.
•Insight: If prefixSum[j] ≡ prefixSum[i] (mod k), then subarray [i, j-1] has sum divisible by k.
•Solution: Track counts of prefix sums modulo k. Same remainders indicate divisible subarrays.
•Complexity: O(n) time, O(k) space.

Problem 3: Product of Array Except Self

•Problem: For each index i, compute the product of all elements except nums[i], without division.
•Insight: Use prefix products (left to right) and suffix products (right to left).
•Solution: result[i] = prefixProduct[i-1] × suffixProduct[i+1]. Two passes, O(1) extra space possible.
•Complexity: O(n) time, O(1) auxiliary space (using output array for intermediate storage).

Pattern Recognition

When you see 'sum of contiguous elements' or 'range query' in a problem, prefix sums should immediately come to mind. The technique is so fundamental that recognizing its applicability becomes second nature with practice.

Summary: Prefix Sums as a Foundation

Prefix sums represent one of the most important array patterns in computer science—simple to implement, mathematically elegant, and universally applicable. Let's consolidate the key insights:

Key Takeaways

•Prefix sums enable O(1) range sum queries after O(n) preprocessing—a fundamental space-time tradeoff.
•The telescoping property allows any range sum to be expressed as the difference of two prefix sums: Sum(i,j) = P[j+1] - P[i].
•Difference arrays are the dual: They enable O(1) range updates where prefix sums enable O(1) range queries.
•The technique extends to 2D (and beyond) using inclusion-exclusion, enabling constant-time rectangular region queries.
•Many problems reduce to prefix sums: Subarray sums, divisibility, counting, and more—with clever use of hash maps for additional power.
•Know when prefix sums aren't enough: For dynamic updates, Fenwick trees and segment trees offer logarithmic complexity for both queries and updates.

What's Next:

With prefix sums mastered, you have a powerful tool for aggregate computations. In the next page, we explore Kadane's Algorithm—an elegant technique for finding the maximum sum subarray that builds on the intuition developed here but takes a fundamentally different approach through dynamic programming.

Pattern Acquired

Prefix sums are now part of your algorithmic toolkit. You'll find them appearing again and again—in competitive programming, system design, and production code. The technique is deceptively simple but remarkably powerful. Master it, and you'll solve entire categories of problems with ease.

1 / 5

Loading learning content...

Data Structures & AlgorithmsCommon Array Patterns & Problem Types

Common Array Patterns & Problem Types

LevelIntermediate

Duration90 mins

TopicCommon Array Patterns & Problem Types

1 / 5

Prefix Sums and Cumulative Arrays

The Power of Precomputation

What You Will Master

The Problem: Repeated Range Queries

Let's formalize the problem that prefix sums solve. Given an array of n elements, we want to efficiently answer multiple queries of the form:

Range Sum Query: "What is the sum of elements from index i to index j (inclusive)?"

This seemingly simple question appears constantly in real-world applications:

Range Query Applications

•Financial analytics — Total sales between two dates, cumulative P&L, running balances
•Time-series databases — Aggregate sensor readings over intervals
•Image processing — Summed area tables for fast region-based calculations
•Game development — Damage calculations, score accumulation, area-of-effect computations
•Network analysis — Bandwidth usage over time windows, packet counts
•Competitive programming — Countless problems reduce to range sum queries

The Naive Approach and Its Limitations

The straightforward solution iterates through the specified range and accumulates the sum:

naiveRangeSum.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// Naive range sum: O(n) per query
function rangeSum(arr: number[], left: number, right: number): number {
    let sum = 0;
    for (let i = left; i <= right; i++) {
        sum += arr[i];
    }
    return sum;
}
 
// Example usage
const data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3];
 
// Query: Sum from index 2 to 7 (inclusive)
const result = rangeSum(data, 2, 7);
console.log(result); // 4 + 1 + 5 + 9 + 2 + 6 = 27

Complexity Analysis of the Naive Approach:

Time per query: O(k), where k = right - left + 1
Worst case: O(n) when querying the entire array
For Q queries: O(Q × n) total time

This might seem acceptable, but consider the scale implications:

Naive Range Sum Query Performance at Scale
Array Size (n)	Queries (Q)	Operations	At 1B ops/sec
1,000	1,000	1 million	1 millisecond
100,000	10,000	1 billion	1 second
1,000,000	100,000	100 billion	100 seconds
10,000,000	1,000,000	10 trillion	~3 hours

The Scale Cliff

The Insight: Cumulative Sums and Telescoping

The breakthrough behind prefix sums comes from a simple mathematical observation. Consider what happens when we compute cumulative sums from the beginning of an array:

For an array A = [a₀, a₁, a₂, a₃, ..., aₙ₋₁], we define the prefix sum array P where:

P[0] = 0 (empty sum, a sentinel value)
P[1] = a₀
P[2] = a₀ + a₁
P[3] = a₀ + a₁ + a₂
...
P[k] = a₀ + a₁ + ... + aₖ₋₁ (sum of first k elements)

The key insight is this: any contiguous range sum can be expressed as the difference of two prefix sums.

The Telescoping Principle

Sum(i to j) = P[j+1] - P[i]

This works because P[j+1] contains the sum from index 0 to j, and P[i] contains the sum from index 0 to i-1. Subtracting cancels all elements before index i, leaving exactly the sum from i to j.

Visual Proof:

Let's trace through this with a concrete example:

Original array A:     [3, 1, 4, 1, 5, 9, 2, 6]
Indices:               0  1  2  3  4  5  6  7

Prefix sum array P:   [0, 3, 4, 8, 9, 14, 23, 25, 31]
Indices:               0  1  2  3  4   5   6   7   8

Query: Sum from index 2 to 5 (inclusive)

Direct calculation: A[2] + A[3] + A[4] + A[5] = 4 + 1 + 5 + 9 = 19
Using prefix sums: P[6] - P[2] = 23 - 4 = 19 ✓

Why does this work?

P[6] = A[0] + A[1] + A[2] + A[3] + A[4] + A[5] = 3 + 1 + 4 + 1 + 5 + 9 = 23
P[2] = A[0] + A[1]                             = 3 + 1             = 4

P[6] - P[2] = (A[0] + A[1] + A[2] + A[3] + A[4] + A[5]) - (A[0] + A[1])
            = A[2] + A[3] + A[4] + A[5]
            = 19

The subtraction telescopes, canceling all terms before our desired range. This is the elegant heart of the prefix sum technique.

Zero-Indexed Prefix Array Convention

We use P of size n+1 with P[0] = 0 as a sentinel. This handles edge cases elegantly: querying from index 0 just becomes P[right+1] - P[0] = P[right+1] - 0 = P[right+1]. No special-case logic needed.

Building the Prefix Sum Array

prefixSumConstruction.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * Build a prefix sum array from the original array.
 * 
 * Time Complexity: O(n) — single pass through the array
 * Space Complexity: O(n) — new array of size n+1
 * 
 * @param arr The original array of numbers
 * @returns Prefix sum array where prefix[i] = sum of arr[0..i-1]
 */
function buildPrefixSum(arr: number[]): number[] {
    const n = arr.length;
    const prefix = new Array(n + 1).fill(0);
    
    // prefix[0] = 0 (sentinel for empty range)
    for (let i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + arr[i];
    }
    
    return prefix;
}
 
// Example
const data = [3, 1, 4, 1, 5, 9, 2, 6];
const prefixSums = buildPrefixSum(data);
 
console.log("Original:", data);
// [3, 1, 4, 1, 5, 9, 2, 6]
 
console.log("Prefix Sums:", prefixSums);
// [0, 3, 4, 8, 9, 14, 23, 25, 31]

Understanding the Recurrence:

The construction follows a simple recurrence relation:

P[0] = 0
P[i] = P[i-1] + A[i-1]   for i = 1, 2, ..., n

This is equivalent to:

P[i] = Σ(k=0 to i-1) A[k]

Each prefix sum builds upon the previous one, adding exactly one new element. This incremental construction is key to the O(n) time complexity.

Memory Optimization: In-Place Prefix Sums

inPlacePrefixSum.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * In-place prefix sum transformation.
 * Modifies the array to contain cumulative sums.
 * 
 * After transformation: arr[i] = sum of original arr[0..i]
 * 
 * Time: O(n), Space: O(1) auxiliary
 */
function prefixSumInPlace(arr: number[]): void {
    for (let i = 1; i < arr.length; i++) {
        arr[i] += arr[i - 1];
    }
}
 
// Example
const data = [3, 1, 4, 1, 5, 9, 2, 6];
prefixSumInPlace(data);
console.log(data);
// [3, 4, 8, 9, 14, 23, 25, 31]
 
// Note: Range query adjustment needed since no sentinel at index 0
// Sum(i to j) = arr[j] - arr[i-1] (handle i=0 specially)

Answering Range Queries in O(1)

With the prefix sum array constructed, any range sum query becomes a simple subtraction—two array accesses and one arithmetic operation:

rangeSumQuery.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Answer a range sum query in O(1) time using prefix sums.
 * 
 * @param prefix The precomputed prefix sum array (size n+1)
 * @param left Starting index of the range (inclusive)
 * @param right Ending index of the range (inclusive)
 * @returns Sum of elements from index left to right
 */
function rangeSum(prefix: number[], left: number, right: number): number {
    return prefix[right + 1] - prefix[left];
}
 
// Complete example
const data = [3, 1, 4, 1, 5, 9, 2, 6];
const prefix = buildPrefixSum(data);
 
// Various range queries — all O(1)
console.log(rangeSum(prefix, 0, 7));  // Entire array: 31
console.log(rangeSum(prefix, 2, 5));  // Indices 2-5: 19
console.log(rangeSum(prefix, 0, 0));  // Single element: 3
console.log(rangeSum(prefix, 4, 7));  // Indices 4-7: 22
console.log(rangeSum(prefix, 3, 3));  // Single element: 1

Complexity Comparison:

Naive vs Prefix Sum: Complexity Analysis
Metric	Naive Approach	Prefix Sum Approach
Preprocessing Time	O(1) (none)	O(n)
Preprocessing Space	O(1)	O(n)
Query Time	O(n) worst case	O(1)
Total for Q Queries	O(Q × n)	O(n + Q)
Update Original Array	O(1)	O(n) to rebuild

The Crossover Point

Handling Edge Cases:

Robust prefix sum implementations must handle several edge cases:

Empty array: Return empty prefix array or handle as error
Single element: Works naturally (P = [0, a₀])
Full array query: P[n] - P[0] = P[n]
Single element query (i=j): P[i+1] - P[i] = A[i] ✓
Invalid indices: Validate left ≤ right and bounds before querying

robustPrefixSum.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/**
 * A complete, production-ready prefix sum implementation
 * with proper validation and error handling.
 */
class PrefixSumArray {
    private prefix: number[];
    private n: number;
    
    constructor(arr: number[]) {
        this.n = arr.length;
        this.prefix = new Array(this.n + 1).fill(0);
        
        for (let i = 0; i < this.n; i++) {
            this.prefix[i + 1] = this.prefix[i] + arr[i];
        }
    }
    
    /**
     * Query the sum of elements in range [left, right] inclusive.
     * @throws Error if indices are out of bounds or invalid
     */
    rangeSum(left: number, right: number): number {
        // Validate indices
        if (left < 0 || right >= this.n) {
            throw new Error(`Index out of bounds: [0, ${this.n - 1}]`);
        }
        if (left > right) {
            throw new Error(`Invalid range: left (${left}) > right (${right})`);
        }
        
        return this.prefix[right + 1] - this.prefix[left];
    }
    
    /**
     * Get the total sum of all elements.
     */
    totalSum(): number {
        return this.prefix[this.n];
    }
    
    /**
     * Get the sum of the first k elements.
     */
    sumFirst(k: number): number {
        if (k < 0 || k > this.n) {
            throw new Error(`k must be in range [0, ${this.n}]`);
        }
        return this.prefix[k];
    }
}

The Space-Time Tradeoff

Prefix sums exemplify a fundamental principle in algorithm design: trading space for time (or equivalently, trading preprocessing for query efficiency).

This tradeoff appears throughout computer science:

Caching: Store computed results to avoid recomputation
Indexing: Build lookup structures to accelerate searches
Memoization: Remember subproblem solutions in dynamic programming
Precomputation tables: Store factorials, powers, combinatorics

Prefix sums represent perhaps the simplest and cleanest example of this tradeoff in action.

What We Pay (Costs)

•O(n) extra space for the prefix array
•O(n) preprocessing time upfront
•O(n) update cost if source data changes
•Memory bandwidth for cache misses on large arrays

What We Gain (Benefits)

•O(1) query time regardless of range size
•O(n + Q) total for Q queries vs O(nQ)
•Simple implementation with low constant factors
•Predictable performance — no worst-case spikes

When Prefix Sums Excel:

Query-heavy workloads: Many queries on static or slowly-changing data
Interactive applications: Real-time analytics, dashboards, games
Batch processing: Answering thousands of range queries in one pass
Competitive programming: Almost always beneficial when range sums appear

When to Reconsider:

Frequent updates: If the source array changes often, rebuilding the prefix array becomes expensive. Consider segment trees or Fenwick trees for O(log n) updates.
Single query: For literally one query, preprocessing isn't worth it.
Memory-constrained environments: When O(n) extra space is prohibitive.
Streaming data: When you can't store the full array anyway.

Dynamic Range Sum Structures

Variation: Difference Arrays for Range Updates

Prefix sums have a powerful dual: the difference array. While prefix sums accelerate range queries, difference arrays accelerate range updates.

The Problem:

Given an array, perform multiple operations of the form:

"Add value v to all elements from index i to j"

Then, reconstruct the final array.

With the naive approach, each range update takes O(k) time where k is the range size. For Q updates: O(Q × n) total.

The Difference Array Solution:

For array A, define difference array D where:

D[0] = A[0]
D[i] = A[i] - A[i-1] for i > 0

The key insight: A range update [i, j] by value v becomes just two point updates in D:

D[i] += v (starting the increment)
D[j+1] -= v (ending the increment)

differenceArray.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/**
 * Difference Array for efficient range updates.
 * 
 * The difference array D encodes the "jumps" between consecutive elements.
 * A range update becomes two point operations.
 * The final array is recovered by computing prefix sums of D.
 */
class DifferenceArray {
    private diff: number[];
    private n: number;
    
    constructor(arr: number[]) {
        this.n = arr.length;
        this.diff = new Array(this.n + 1).fill(0);
        
        // Build difference array
        this.diff[0] = arr[0];
        for (let i = 1; i < this.n; i++) {
            this.diff[i] = arr[i] - arr[i - 1];
        }
    }
    
    /**
     * Add value to all elements in range [left, right] inclusive.
     * Time: O(1)
     */
    rangeUpdate(left: number, right: number, value: number): void {
        this.diff[left] += value;
        if (right + 1 < this.n) {
            this.diff[right + 1] -= value;
        }
    }
    
    /**
     * Reconstruct the final array after all updates.
     * Time: O(n) — essentially computing prefix sums
     */
    getResult(): number[] {
        const result = new Array(this.n);
        result[0] = this.diff[0];
        
        for (let i = 1; i < this.n; i++) {
            result[i] = result[i - 1] + this.diff[i];
        }
        
        return result;
    }
}
 
// Example: Apply multiple range updates
const initial = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0];
const da = new DifferenceArray(initial);
 
da.rangeUpdate(2, 5, 10);   // Add 10 to indices 2-5
da.rangeUpdate(3, 8, 5);    // Add 5 to indices 3-8
da.rangeUpdate(0, 4, -3);   // Subtract 3 from indices 0-4
 
console.log(da.getResult());
// [-3, -3, 7, 12, 12, 15, 5, 5, 5, 0]

The Beautiful Duality

Prefix Sum vs Difference Array
Technique	Fast Operation	Slow Operation	Primary Use
Prefix Sum	Range Query O(1)	Point Update O(n)	Many queries, few updates
Difference Array	Range Update O(1)	Point Query O(n)	Many updates, few queries

Extension: 2D Prefix Sums (Summed Area Tables)

The prefix sum concept extends naturally to two dimensions, creating what are known as 2D prefix sums or summed area tables (a term from image processing).

The Problem:

Given a 2D matrix of values, answer queries of the form:

"What is the sum of all elements in the rectangular region from (r1, c1) to (r2, c2)?"

The 2D Prefix Sum Construction:

For matrix M, build prefix sum matrix P where P[i][j] = sum of all elements in the rectangle from (0,0) to (i-1, j-1).

The construction uses the inclusion-exclusion principle:

P[i][j] = M[i-1][j-1] + P[i-1][j] + P[i][j-1] - P[i-1][j-1]

Add the cell above
Add the cell to the left
Subtract the diagonal (counted twice)
Add the current matrix element

twoDPrefixSum.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
/**
 * 2D Prefix Sum (Summed Area Table) for O(1) rectangular region sum queries.
 */
class PrefixSum2D {
    private prefix: number[][];
    private rows: number;
    private cols: number;
    
    constructor(matrix: number[][]) {
        if (matrix.length === 0 || matrix[0].length === 0) {
            this.rows = 0;
            this.cols = 0;
            this.prefix = [];
            return;
        }
        
        this.rows = matrix.length;
        this.cols = matrix[0].length;
        
        // Create prefix sum matrix with sentinel row and column
        this.prefix = Array.from(
            { length: this.rows + 1 },
            () => new Array(this.cols + 1).fill(0)
        );
        
        // Build using inclusion-exclusion
        for (let i = 1; i <= this.rows; i++) {
            for (let j = 1; j <= this.cols; 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];
            }
        }
    }
    
    /**
     * Query sum of rectangular region from (r1,c1) to (r2,c2) inclusive.
     * Uses inclusion-exclusion to compute in O(1).
     */
    regionSum(r1: number, c1: number, r2: number, c2: number): number {
        // Convert to 1-indexed prefix array coordinates
        r1++; c1++; r2++; c2++;
        
        return this.prefix[r2][c2]
            - this.prefix[r1 - 1][c2]
            - this.prefix[r2][c1 - 1]
            + this.prefix[r1 - 1][c1 - 1];
    }
}
 
// Example
const matrix = [
    [1, 2, 3, 4],
    [5, 6, 7, 8],
    [9, 10, 11, 12]
];
 
const ps2d = new PrefixSum2D(matrix);
 
// Sum of entire matrix
console.log(ps2d.regionSum(0, 0, 2, 3)); // 78
 
// Sum of middle 2x2 region (rows 0-1, cols 1-2)
console.log(ps2d.regionSum(0, 1, 1, 2)); // 2+3+6+7 = 18

Image Processing Origins

Complexity Analysis:

Preprocessing: O(m × n) time and space for an m × n matrix
Query: O(1) per rectangular region query
Extension: The technique generalizes to N dimensions with O(2^N) terms in the inclusion-exclusion formula, though practical use beyond 3D is rare.

Classic Problems Using Prefix Sums

Prefix sums unlock efficient solutions to a wide variety of problems. Here are several classics that every serious programmer should know:

Problem 1: Count Subarrays with Given Sum

•Problem: Count how many contiguous subarrays have sum equal to k.
•Insight: If prefixSum[j] - prefixSum[i] = k, then subarray [i, j-1] has sum k.
•Solution: Use a hash map to count prefix sum occurrences. For each new prefix sum, check how many previous prefix sums equal (current - k).
•Complexity: O(n) time, O(n) space.

subarraySum.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * Count subarrays with sum equal to k.
 * Uses prefix sums + hash map for O(n) solution.
 */
function subarraySum(nums: number[], k: number): number {
    const prefixCount = new Map<number, number>();
    prefixCount.set(0, 1); // Empty prefix has sum 0
    
    let count = 0;
    let currentSum = 0;
    
    for (const num of nums) {
        currentSum += num;
        
        // How many previous prefix sums equal (currentSum - k)?
        const target = currentSum - k;
        if (prefixCount.has(target)) {
            count += prefixCount.get(target)!;
        }
        
        // Record this prefix sum
        prefixCount.set(currentSum, (prefixCount.get(currentSum) || 0) + 1);
    }
    
    return count;
}
 
console.log(subarraySum([1, 1, 1], 2)); // 2
console.log(subarraySum([1, 2, 3], 3)); // 2

Problem 2: Subarray Divisibility

•Problem: Count subarrays whose sum is divisible by k.
•Insight: If prefixSum[j] ≡ prefixSum[i] (mod k), then subarray [i, j-1] has sum divisible by k.
•Solution: Track counts of prefix sums modulo k. Same remainders indicate divisible subarrays.
•Complexity: O(n) time, O(k) space.

Problem 3: Product of Array Except Self

•Problem: For each index i, compute the product of all elements except nums[i], without division.
•Insight: Use prefix products (left to right) and suffix products (right to left).
•Solution: result[i] = prefixProduct[i-1] × suffixProduct[i+1]. Two passes, O(1) extra space possible.
•Complexity: O(n) time, O(1) auxiliary space (using output array for intermediate storage).

Pattern Recognition

Summary: Prefix Sums as a Foundation

Prefix sums represent one of the most important array patterns in computer science—simple to implement, mathematically elegant, and universally applicable. Let's consolidate the key insights:

Key Takeaways

•Prefix sums enable O(1) range sum queries after O(n) preprocessing—a fundamental space-time tradeoff.
•The telescoping property allows any range sum to be expressed as the difference of two prefix sums: Sum(i,j) = P[j+1] - P[i].
•Difference arrays are the dual: They enable O(1) range updates where prefix sums enable O(1) range queries.
•The technique extends to 2D (and beyond) using inclusion-exclusion, enabling constant-time rectangular region queries.
•Many problems reduce to prefix sums: Subarray sums, divisibility, counting, and more—with clever use of hash maps for additional power.
•Know when prefix sums aren't enough: For dynamic updates, Fenwick trees and segment trees offer logarithmic complexity for both queries and updates.

What's Next:

Pattern Acquired

1 / 5