Overview#

Prefix Sum is a preprocessing technique: first store the cumulative value from the beginning to the current position, then the sum of any contiguous interval can be obtained by subtracting the results of two queries.

Prerequisites

• Array indexing: The prefix array usually has one extra slot to reduce boundary-handling overhead
• Interval representation: Clearly distinguish the difference between [l, r] and [l, r)
• Hash map: Used to count prefix sum occurrences, solving “subarrays with sum K”

Problem Definition#

Given an array and multiple interval queries, quickly compute the sum or related cumulative value of any contiguous interval.

Core Principle: Step-by-Step Illustration#

Using the array [1, 3, 5, 2, 4] as an example:

1
nums:    1   3   5   2   4
2
index:   0   1   2   3   4
3
prefix: 0   1   4   9   11  15

Querying the interval nums[1..3]:

1
prefix[4] - prefix[1] = 11 - 1 = 10
2
nums[1] + nums[2] + nums[3] = 3 + 5 + 2 = 10

The advantage of having one extra slot prefix[0] = 0 is that intervals starting from index 0 can also use the same formula.

Detailed Algorithm Steps#

1
Algorithm: PrefixSum(nums)
2
Input: array nums
3
Output: prefix array that allows O(1) range sum queries
4

5
1. Create an array prefix of length nums.length + 1, initialized to 0
6
2. for i from 0 to nums.length - 1:
7
3.     prefix[i + 1] ← prefix[i] + nums[i]
8
4. When querying [l, r], return prefix[r + 1] - prefix[l]

Complexity analysis:

TypeScript Implementation#

1
function buildPrefixSum(nums: number[]): number[] {
2
  const prefix = new Array(nums.length + 1).fill(0);
3

4
  for (let i = 0; i < nums.length; i++) {
5
    prefix[i + 1] = prefix[i] + nums[i];
6
  }
7

8
  return prefix;
9
}
10

11
function rangeSum(prefix: number[], left: number, right: number): number {
12
  return prefix[right + 1] - prefix[left];
13
}

1
class NumArray {
2
  private prefix: number[];
3

4
  constructor(nums: number[]) {
5
    this.prefix = buildPrefixSum(nums);
6
  }
7

8
  sumRange(left: number, right: number): number {
9
    return this.prefix[right + 1] - this.prefix[left];
10
  }
11
}

1
function subarraySum(nums: number[], k: number): number {
2
  const countByPrefix = new Map<number, number>();
3
  countByPrefix.set(0, 1);
4

5
  let prefix = 0;
6
  let count = 0;
7

8
  for (const num of nums) {
9
    prefix += num;
10
    count += countByPrefix.get(prefix - k) ?? 0;
11
    countByPrefix.set(prefix, (countByPrefix.get(prefix) ?? 0) + 1);
12
  }
13

14
  return count;
15
}

1
function maxSubArray(nums: number[]): number {
2
  let prefix = 0;
3
  let minPrefix = 0;
4
  let best = nums[0];
5

6
  for (const num of nums) {
7
    prefix += num;
8
    best = Math.max(best, prefix - minPrefix);
9
    minPrefix = Math.min(minPrefix, prefix);
10
  }
11

12
  return best;
13
}

1
function productExceptSelf(nums: number[]): number[] {
2
  const result = new Array(nums.length).fill(1);
3

4
  let leftProduct = 1;
5
  for (let i = 0; i < nums.length; i++) {
6
    result[i] = leftProduct;
7
    leftProduct *= nums[i];
8
  }
9

10
  let rightProduct = 1;
11
  for (let i = nums.length - 1; i >= 0; i--) {
12
    result[i] *= rightProduct;
13
    rightProduct *= nums[i];
14
  }
15

16
  return result;
17
}

Engineering Optimization: Unifying Interval Semantics#

The most common bugs in prefix sums come from endpoint confusion. It is recommended to consistently use the pattern of “prefix array with one extra slot + querying the closed interval [left, right]”.

If the array is modified frequently, ordinary prefix sums require rebuilding after every update, so you should switch to a data structure that supports dynamic updates.

Applications and Limitations#

Summary#

Key points:

1. Prefix sum = preprocessing cumulative values + O(1) interval queries.
2. Having one extra slot prefix[0] = 0 unifies the boundary formula.
3. Prefix sum + hash map is the core model for “subarrays with sum K”.
4. Use prefix sums for static queries; consider a Fenwick tree or segment tree for dynamic updates.